2 * Copyright 2011 Leiden University. All rights reserved.
3 * Copyright 2012-2015 Ecole Normale Superieure. All rights reserved.
4 * Copyright 2015-2016 Sven Verdoolaege. All rights reserved.
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions
10 * 1. Redistributions of source code must retain the above copyright
11 * notice, this list of conditions and the following disclaimer.
13 * 2. Redistributions in binary form must reproduce the above
14 * copyright notice, this list of conditions and the following
15 * disclaimer in the documentation and/or other materials provided
16 * with the distribution.
18 * THIS SOFTWARE IS PROVIDED BY LEIDEN UNIVERSITY ''AS IS'' AND ANY
19 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
20 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
21 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL LEIDEN UNIVERSITY OR
22 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
23 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
24 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA,
25 * OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
26 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
27 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
30 * The views and conclusions contained in the software and documentation
31 * are those of the authors and should not be interpreted as
32 * representing official policies, either expressed or implied, of
43 #include <llvm/Support/raw_ostream.h>
44 #include <clang/AST/ASTContext.h>
45 #include <clang/AST/ASTDiagnostic.h>
46 #include <clang/AST/Attr.h>
47 #include <clang/AST/Expr.h>
48 #include <clang/AST/RecursiveASTVisitor.h>
51 #include <isl/space.h>
54 #include <isl/union_set.h>
61 #include "expr_plus.h"
64 #include "killed_locals.h"
69 #include "scop_plus.h"
70 #include "substituter.h"
72 #include "tree2scop.h"
75 using namespace clang
;
77 static enum pet_op_type
UnaryOperatorKind2pet_op_type(UnaryOperatorKind kind
)
87 return pet_op_post_inc
;
89 return pet_op_post_dec
;
91 return pet_op_pre_inc
;
93 return pet_op_pre_dec
;
99 static enum pet_op_type
BinaryOperatorKind2pet_op_type(BinaryOperatorKind kind
)
103 return pet_op_add_assign
;
105 return pet_op_sub_assign
;
107 return pet_op_mul_assign
;
109 return pet_op_div_assign
;
111 return pet_op_and_assign
;
113 return pet_op_xor_assign
;
115 return pet_op_or_assign
;
117 return pet_op_assign
;
159 #ifdef GETTYPEINFORETURNSTYPEINFO
161 static int size_in_bytes(ASTContext
&context
, QualType type
)
163 return context
.getTypeInfo(type
).Width
/ 8;
168 static int size_in_bytes(ASTContext
&context
, QualType type
)
170 return context
.getTypeInfo(type
).first
/ 8;
175 /* Check if the element type corresponding to the given array type
176 * has a const qualifier.
178 static bool const_base(QualType qt
)
180 const Type
*type
= qt
.getTypePtr();
182 if (type
->isPointerType())
183 return const_base(type
->getPointeeType());
184 if (type
->isArrayType()) {
185 const ArrayType
*atype
;
186 type
= type
->getCanonicalTypeInternal().getTypePtr();
187 atype
= cast
<ArrayType
>(type
);
188 return const_base(atype
->getElementType());
191 return qt
.isConstQualified();
196 std::map
<const Type
*, pet_expr
*>::iterator it
;
197 std::map
<FunctionDecl
*, pet_function_summary
*>::iterator it_s
;
199 for (it
= type_size
.begin(); it
!= type_size
.end(); ++it
)
200 pet_expr_free(it
->second
);
201 for (it_s
= summary_cache
.begin(); it_s
!= summary_cache
.end(); ++it_s
)
202 pet_function_summary_free(it_s
->second
);
204 isl_id_to_pet_expr_free(id_size
);
205 isl_union_map_free(value_bounds
);
208 /* Report a diagnostic on the range "range", unless autodetect is set.
210 void PetScan::report(SourceRange range
, unsigned id
)
212 if (options
->autodetect
)
215 SourceLocation loc
= range
.getBegin();
216 DiagnosticsEngine
&diag
= PP
.getDiagnostics();
217 DiagnosticBuilder B
= diag
.Report(loc
, id
) << range
;
220 /* Report a diagnostic on "stmt", unless autodetect is set.
222 void PetScan::report(Stmt
*stmt
, unsigned id
)
224 report(stmt
->getSourceRange(), id
);
227 /* Report a diagnostic on "decl", unless autodetect is set.
229 void PetScan::report(Decl
*decl
, unsigned id
)
231 report(decl
->getSourceRange(), id
);
234 /* Called if we found something we (currently) cannot handle.
235 * We'll provide more informative warnings later.
237 * We only actually complain if autodetect is false.
239 void PetScan::unsupported(Stmt
*stmt
)
241 DiagnosticsEngine
&diag
= PP
.getDiagnostics();
242 unsigned id
= diag
.getCustomDiagID(DiagnosticsEngine::Warning
,
247 /* Report an unsupported unary operator, unless autodetect is set.
249 void PetScan::report_unsupported_unary_operator(Stmt
*stmt
)
251 DiagnosticsEngine
&diag
= PP
.getDiagnostics();
252 unsigned id
= diag
.getCustomDiagID(DiagnosticsEngine::Warning
,
253 "this type of unary operator is not supported");
257 /* Report an unsupported binary operator, unless autodetect is set.
259 void PetScan::report_unsupported_binary_operator(Stmt
*stmt
)
261 DiagnosticsEngine
&diag
= PP
.getDiagnostics();
262 unsigned id
= diag
.getCustomDiagID(DiagnosticsEngine::Warning
,
263 "this type of binary operator is not supported");
267 /* Report an unsupported statement type, unless autodetect is set.
269 void PetScan::report_unsupported_statement_type(Stmt
*stmt
)
271 DiagnosticsEngine
&diag
= PP
.getDiagnostics();
272 unsigned id
= diag
.getCustomDiagID(DiagnosticsEngine::Warning
,
273 "this type of statement is not supported");
277 /* Report a missing prototype, unless autodetect is set.
279 void PetScan::report_prototype_required(Stmt
*stmt
)
281 DiagnosticsEngine
&diag
= PP
.getDiagnostics();
282 unsigned id
= diag
.getCustomDiagID(DiagnosticsEngine::Warning
,
283 "prototype required");
287 /* Report a missing increment, unless autodetect is set.
289 void PetScan::report_missing_increment(Stmt
*stmt
)
291 DiagnosticsEngine
&diag
= PP
.getDiagnostics();
292 unsigned id
= diag
.getCustomDiagID(DiagnosticsEngine::Warning
,
293 "missing increment");
297 /* Report a missing summary function, unless autodetect is set.
299 void PetScan::report_missing_summary_function(Stmt
*stmt
)
301 DiagnosticsEngine
&diag
= PP
.getDiagnostics();
302 unsigned id
= diag
.getCustomDiagID(DiagnosticsEngine::Warning
,
303 "missing summary function");
307 /* Report a missing summary function body, unless autodetect is set.
309 void PetScan::report_missing_summary_function_body(Stmt
*stmt
)
311 DiagnosticsEngine
&diag
= PP
.getDiagnostics();
312 unsigned id
= diag
.getCustomDiagID(DiagnosticsEngine::Warning
,
313 "missing summary function body");
317 /* Report an unsupported argument in a call to an inlined function,
318 * unless autodetect is set.
320 void PetScan::report_unsupported_inline_function_argument(Stmt
*stmt
)
322 DiagnosticsEngine
&diag
= PP
.getDiagnostics();
323 unsigned id
= diag
.getCustomDiagID(DiagnosticsEngine::Warning
,
324 "unsupported inline function call argument");
328 /* Report an unsupported type of declaration, unless autodetect is set.
330 void PetScan::report_unsupported_declaration(Decl
*decl
)
332 DiagnosticsEngine
&diag
= PP
.getDiagnostics();
333 unsigned id
= diag
.getCustomDiagID(DiagnosticsEngine::Warning
,
334 "unsupported declaration");
338 /* Report an unbalanced pair of scop/endscop pragmas, unless autodetect is set.
340 void PetScan::report_unbalanced_pragmas(SourceLocation scop
,
341 SourceLocation endscop
)
343 if (options
->autodetect
)
346 DiagnosticsEngine
&diag
= PP
.getDiagnostics();
348 unsigned id
= diag
.getCustomDiagID(DiagnosticsEngine::Warning
,
349 "unbalanced endscop pragma");
350 DiagnosticBuilder B2
= diag
.Report(endscop
, id
);
353 unsigned id
= diag
.getCustomDiagID(DiagnosticsEngine::Note
,
354 "corresponding scop pragma");
355 DiagnosticBuilder B
= diag
.Report(scop
, id
);
359 /* Extract an integer from "val", which is assumed to be non-negative.
361 static __isl_give isl_val
*extract_unsigned(isl_ctx
*ctx
,
362 const llvm::APInt
&val
)
365 const uint64_t *data
;
367 data
= val
.getRawData();
368 n
= val
.getNumWords();
369 return isl_val_int_from_chunks(ctx
, n
, sizeof(uint64_t), data
);
372 /* Extract an integer from "val". If "is_signed" is set, then "val"
373 * is signed. Otherwise it it unsigned.
375 static __isl_give isl_val
*extract_int(isl_ctx
*ctx
, bool is_signed
,
378 int is_negative
= is_signed
&& val
.isNegative();
384 v
= extract_unsigned(ctx
, val
);
391 /* Extract an integer from "expr".
393 __isl_give isl_val
*PetScan::extract_int(isl_ctx
*ctx
, IntegerLiteral
*expr
)
395 const Type
*type
= expr
->getType().getTypePtr();
396 bool is_signed
= type
->hasSignedIntegerRepresentation();
398 return ::extract_int(ctx
, is_signed
, expr
->getValue());
401 /* Extract an integer from "expr".
402 * Return NULL if "expr" does not (obviously) represent an integer.
404 __isl_give isl_val
*PetScan::extract_int(clang::ParenExpr
*expr
)
406 return extract_int(expr
->getSubExpr());
409 /* Extract an integer from "expr".
410 * Return NULL if "expr" does not (obviously) represent an integer.
412 __isl_give isl_val
*PetScan::extract_int(clang::Expr
*expr
)
414 if (expr
->getStmtClass() == Stmt::IntegerLiteralClass
)
415 return extract_int(ctx
, cast
<IntegerLiteral
>(expr
));
416 if (expr
->getStmtClass() == Stmt::ParenExprClass
)
417 return extract_int(cast
<ParenExpr
>(expr
));
423 /* Extract a pet_expr from the APInt "val", which is assumed
424 * to be non-negative.
426 __isl_give pet_expr
*PetScan::extract_expr(const llvm::APInt
&val
)
428 return pet_expr_new_int(extract_unsigned(ctx
, val
));
431 /* Return the number of bits needed to represent the type of "decl",
432 * if it is an integer type. Otherwise return 0.
433 * If qt is signed then return the opposite of the number of bits.
435 static int get_type_size(ValueDecl
*decl
)
437 return pet_clang_get_type_size(decl
->getType(), decl
->getASTContext());
440 /* Bound parameter "pos" of "set" to the possible values of "decl".
442 static __isl_give isl_set
*set_parameter_bounds(__isl_take isl_set
*set
,
443 unsigned pos
, ValueDecl
*decl
)
449 ctx
= isl_set_get_ctx(set
);
450 type_size
= get_type_size(decl
);
452 isl_die(ctx
, isl_error_invalid
, "not an integer type",
453 return isl_set_free(set
));
455 set
= isl_set_lower_bound_si(set
, isl_dim_param
, pos
, 0);
456 bound
= isl_val_int_from_ui(ctx
, type_size
);
457 bound
= isl_val_2exp(bound
);
458 bound
= isl_val_sub_ui(bound
, 1);
459 set
= isl_set_upper_bound_val(set
, isl_dim_param
, pos
, bound
);
461 bound
= isl_val_int_from_ui(ctx
, -type_size
- 1);
462 bound
= isl_val_2exp(bound
);
463 bound
= isl_val_sub_ui(bound
, 1);
464 set
= isl_set_upper_bound_val(set
, isl_dim_param
, pos
,
465 isl_val_copy(bound
));
466 bound
= isl_val_neg(bound
);
467 bound
= isl_val_sub_ui(bound
, 1);
468 set
= isl_set_lower_bound_val(set
, isl_dim_param
, pos
, bound
);
474 __isl_give pet_expr
*PetScan::extract_index_expr(ImplicitCastExpr
*expr
)
476 return extract_index_expr(expr
->getSubExpr());
479 /* Construct a pet_expr representing an index expression for an access
480 * to the variable referenced by "expr".
482 * If "expr" references an enum constant, then return an integer expression
483 * instead, representing the value of the enum constant.
485 __isl_give pet_expr
*PetScan::extract_index_expr(DeclRefExpr
*expr
)
487 return extract_index_expr(expr
->getDecl());
490 /* Construct a pet_expr representing an index expression for an access
491 * to the variable "decl".
493 * If "decl" is an enum constant, then we return an integer expression
494 * instead, representing the value of the enum constant.
496 __isl_give pet_expr
*PetScan::extract_index_expr(ValueDecl
*decl
)
500 if (isa
<EnumConstantDecl
>(decl
))
501 return extract_expr(cast
<EnumConstantDecl
>(decl
));
503 id
= pet_id_from_decl(ctx
, decl
);
504 return pet_id_create_index_expr(id
);
507 /* Construct a pet_expr representing the index expression "expr"
508 * Return NULL on error.
510 * If "expr" is a reference to an enum constant, then return
511 * an integer expression instead, representing the value of the enum constant.
513 __isl_give pet_expr
*PetScan::extract_index_expr(Expr
*expr
)
515 switch (expr
->getStmtClass()) {
516 case Stmt::ImplicitCastExprClass
:
517 return extract_index_expr(cast
<ImplicitCastExpr
>(expr
));
518 case Stmt::DeclRefExprClass
:
519 return extract_index_expr(cast
<DeclRefExpr
>(expr
));
520 case Stmt::ArraySubscriptExprClass
:
521 return extract_index_expr(cast
<ArraySubscriptExpr
>(expr
));
522 case Stmt::IntegerLiteralClass
:
523 return extract_expr(cast
<IntegerLiteral
>(expr
));
524 case Stmt::MemberExprClass
:
525 return extract_index_expr(cast
<MemberExpr
>(expr
));
532 /* Extract an index expression from the given array subscript expression.
534 * We first extract an index expression from the base.
535 * This will result in an index expression with a range that corresponds
536 * to the earlier indices.
537 * We then extract the current index and let
538 * pet_expr_access_subscript combine the two.
540 __isl_give pet_expr
*PetScan::extract_index_expr(ArraySubscriptExpr
*expr
)
542 Expr
*base
= expr
->getBase();
543 Expr
*idx
= expr
->getIdx();
547 base_expr
= extract_index_expr(base
);
548 index
= extract_expr(idx
);
550 base_expr
= pet_expr_access_subscript(base_expr
, index
);
555 /* Extract an index expression from a member expression.
557 * If the base access (to the structure containing the member)
562 * and the member is called "f", then the member access is of
567 * If the member access is to an anonymous struct, then simply return
571 * If the member access in the source code is of the form
575 * then it is treated as
579 __isl_give pet_expr
*PetScan::extract_index_expr(MemberExpr
*expr
)
581 Expr
*base
= expr
->getBase();
582 FieldDecl
*field
= cast
<FieldDecl
>(expr
->getMemberDecl());
583 pet_expr
*base_index
;
586 base_index
= extract_index_expr(base
);
588 if (expr
->isArrow()) {
589 pet_expr
*index
= pet_expr_new_int(isl_val_zero(ctx
));
590 base_index
= pet_expr_access_subscript(base_index
, index
);
593 if (field
->isAnonymousStructOrUnion())
596 id
= pet_id_from_decl(ctx
, field
);
598 return pet_expr_access_member(base_index
, id
);
601 /* Mark the given access pet_expr as a write.
603 static __isl_give pet_expr
*mark_write(__isl_take pet_expr
*access
)
605 access
= pet_expr_access_set_write(access
, 1);
606 access
= pet_expr_access_set_read(access
, 0);
611 /* Mark the given (read) access pet_expr as also possibly being written.
612 * That is, initialize the may write access relation from the may read relation
613 * and initialize the must write access relation to the empty relation.
615 static __isl_give pet_expr
*mark_may_write(__isl_take pet_expr
*expr
)
617 isl_union_map
*access
;
618 isl_union_map
*empty
;
620 access
= pet_expr_access_get_dependent_access(expr
,
621 pet_expr_access_may_read
);
622 empty
= isl_union_map_empty(isl_union_map_get_space(access
));
623 expr
= pet_expr_access_set_access(expr
, pet_expr_access_may_write
,
625 expr
= pet_expr_access_set_access(expr
, pet_expr_access_must_write
,
631 /* Construct a pet_expr representing a unary operator expression.
633 __isl_give pet_expr
*PetScan::extract_expr(UnaryOperator
*expr
)
639 op
= UnaryOperatorKind2pet_op_type(expr
->getOpcode());
640 if (op
== pet_op_last
) {
641 report_unsupported_unary_operator(expr
);
645 arg
= extract_expr(expr
->getSubExpr());
647 if (expr
->isIncrementDecrementOp() &&
648 pet_expr_get_type(arg
) == pet_expr_access
) {
649 arg
= mark_write(arg
);
650 arg
= pet_expr_access_set_read(arg
, 1);
653 type_size
= pet_clang_get_type_size(expr
->getType(), ast_context
);
654 return pet_expr_new_unary(type_size
, op
, arg
);
657 /* Construct a pet_expr representing a binary operator expression.
659 * If the top level operator is an assignment and the LHS is an access,
660 * then we mark that access as a write. If the operator is a compound
661 * assignment, the access is marked as both a read and a write.
663 __isl_give pet_expr
*PetScan::extract_expr(BinaryOperator
*expr
)
669 op
= BinaryOperatorKind2pet_op_type(expr
->getOpcode());
670 if (op
== pet_op_last
) {
671 report_unsupported_binary_operator(expr
);
675 lhs
= extract_expr(expr
->getLHS());
676 rhs
= extract_expr(expr
->getRHS());
678 if (expr
->isAssignmentOp() &&
679 pet_expr_get_type(lhs
) == pet_expr_access
) {
680 lhs
= mark_write(lhs
);
681 if (expr
->isCompoundAssignmentOp())
682 lhs
= pet_expr_access_set_read(lhs
, 1);
685 type_size
= pet_clang_get_type_size(expr
->getType(), ast_context
);
686 return pet_expr_new_binary(type_size
, op
, lhs
, rhs
);
689 /* Construct a pet_tree for a variable declaration and
690 * add the declaration to the list of declarations
691 * inside the current compound statement.
693 __isl_give pet_tree
*PetScan::extract(Decl
*decl
)
699 if (!isa
<VarDecl
>(decl
)) {
700 report_unsupported_declaration(decl
);
704 vd
= cast
<VarDecl
>(decl
);
705 declarations
.push_back(vd
);
707 lhs
= extract_access_expr(vd
);
708 lhs
= mark_write(lhs
);
710 tree
= pet_tree_new_decl(lhs
);
712 rhs
= extract_expr(vd
->getInit());
713 tree
= pet_tree_new_decl_init(lhs
, rhs
);
719 /* Construct a pet_tree for a variable declaration statement.
720 * If the declaration statement declares multiple variables,
721 * then return a group of pet_trees, one for each declared variable.
723 __isl_give pet_tree
*PetScan::extract(DeclStmt
*stmt
)
728 if (!stmt
->isSingleDecl()) {
729 const DeclGroup
&group
= stmt
->getDeclGroup().getDeclGroup();
731 tree
= pet_tree_new_block(ctx
, 0, n
);
733 for (unsigned i
= 0; i
< n
; ++i
) {
737 tree_i
= extract(group
[i
]);
738 loc
= construct_pet_loc(group
[i
]->getSourceRange(),
740 tree_i
= pet_tree_set_loc(tree_i
, loc
);
741 tree
= pet_tree_block_add_child(tree
, tree_i
);
747 return extract(stmt
->getSingleDecl());
750 /* Construct a pet_expr representing a conditional operation.
752 __isl_give pet_expr
*PetScan::extract_expr(ConditionalOperator
*expr
)
754 pet_expr
*cond
, *lhs
, *rhs
;
756 cond
= extract_expr(expr
->getCond());
757 lhs
= extract_expr(expr
->getTrueExpr());
758 rhs
= extract_expr(expr
->getFalseExpr());
760 return pet_expr_new_ternary(cond
, lhs
, rhs
);
763 __isl_give pet_expr
*PetScan::extract_expr(ImplicitCastExpr
*expr
)
765 return extract_expr(expr
->getSubExpr());
768 /* Construct a pet_expr representing a floating point value.
770 * If the floating point literal does not appear in a macro,
771 * then we use the original representation in the source code
772 * as the string representation. Otherwise, we use the pretty
773 * printer to produce a string representation.
775 __isl_give pet_expr
*PetScan::extract_expr(FloatingLiteral
*expr
)
779 const LangOptions
&LO
= PP
.getLangOpts();
780 SourceLocation loc
= expr
->getLocation();
782 if (!loc
.isMacroID()) {
783 SourceManager
&SM
= PP
.getSourceManager();
784 unsigned len
= Lexer::MeasureTokenLength(loc
, SM
, LO
);
785 s
= string(SM
.getCharacterData(loc
), len
);
787 llvm::raw_string_ostream
S(s
);
788 expr
->printPretty(S
, 0, PrintingPolicy(LO
));
791 d
= expr
->getValueAsApproximateDouble();
792 return pet_expr_new_double(ctx
, d
, s
.c_str());
795 /* Extract an index expression from "expr" and then convert it into
796 * an access pet_expr.
798 * If "expr" is a reference to an enum constant, then return
799 * an integer expression instead, representing the value of the enum constant.
801 __isl_give pet_expr
*PetScan::extract_access_expr(Expr
*expr
)
805 index
= extract_index_expr(expr
);
807 if (pet_expr_get_type(index
) == pet_expr_int
)
810 return pet_expr_access_from_index(expr
->getType(), index
, ast_context
);
813 /* Extract an index expression from "decl" and then convert it into
814 * an access pet_expr.
816 __isl_give pet_expr
*PetScan::extract_access_expr(ValueDecl
*decl
)
818 return pet_expr_access_from_index(decl
->getType(),
819 extract_index_expr(decl
), ast_context
);
822 __isl_give pet_expr
*PetScan::extract_expr(ParenExpr
*expr
)
824 return extract_expr(expr
->getSubExpr());
827 /* Extract an assume statement from the argument "expr"
828 * of a __builtin_assume or __pencil_assume statement.
830 __isl_give pet_expr
*PetScan::extract_assume(Expr
*expr
)
832 return pet_expr_new_unary(0, pet_op_assume
, extract_expr(expr
));
835 /* If "expr" is an address-of operator, then return its argument.
836 * Otherwise, return NULL.
838 static Expr
*extract_addr_of_arg(Expr
*expr
)
842 if (expr
->getStmtClass() != Stmt::UnaryOperatorClass
)
844 op
= cast
<UnaryOperator
>(expr
);
845 if (op
->getOpcode() != UO_AddrOf
)
847 return op
->getSubExpr();
850 /* Construct a pet_expr corresponding to the function call argument "expr".
851 * The argument appears in position "pos" of a call to function "fd".
853 * If we are passing along a pointer to an array element
854 * or an entire row or even higher dimensional slice of an array,
855 * then the function being called may write into the array.
857 * We assume here that if the function is declared to take a pointer
858 * to a const type, then the function may only perform a read
859 * and that otherwise, it may either perform a read or a write (or both).
860 * We only perform this check if "detect_writes" is set.
862 __isl_give pet_expr
*PetScan::extract_argument(FunctionDecl
*fd
, int pos
,
863 Expr
*expr
, bool detect_writes
)
867 int is_addr
= 0, is_partial
= 0;
869 expr
= pet_clang_strip_casts(expr
);
870 arg
= extract_addr_of_arg(expr
);
875 res
= extract_expr(expr
);
878 if (pet_clang_array_depth(expr
->getType()) > 0)
880 if (detect_writes
&& (is_addr
|| is_partial
) &&
881 pet_expr_get_type(res
) == pet_expr_access
) {
883 if (!fd
->hasPrototype()) {
884 report_prototype_required(expr
);
885 return pet_expr_free(res
);
887 parm
= fd
->getParamDecl(pos
);
888 if (!const_base(parm
->getType()))
889 res
= mark_may_write(res
);
893 res
= pet_expr_new_unary(0, pet_op_address_of
, res
);
897 /* Find the first FunctionDecl with the given name.
898 * "call" is the corresponding call expression and is only used
899 * for reporting errors.
901 * Return NULL on error.
903 FunctionDecl
*PetScan::find_decl_from_name(CallExpr
*call
, string name
)
905 TranslationUnitDecl
*tu
= ast_context
.getTranslationUnitDecl();
906 DeclContext::decl_iterator begin
= tu
->decls_begin();
907 DeclContext::decl_iterator end
= tu
->decls_end();
908 for (DeclContext::decl_iterator i
= begin
; i
!= end
; ++i
) {
909 FunctionDecl
*fd
= dyn_cast
<FunctionDecl
>(*i
);
912 if (fd
->getName().str().compare(name
) != 0)
916 report_missing_summary_function_body(call
);
919 report_missing_summary_function(call
);
923 /* Return the FunctionDecl for the summary function associated to the
924 * function called by "call".
926 * In particular, if the pencil option is set, then
927 * search for an annotate attribute formatted as
928 * "pencil_access(name)", where "name" is the name of the summary function.
930 * If no summary function was specified, then return the FunctionDecl
931 * that is actually being called.
933 * Return NULL on error.
935 FunctionDecl
*PetScan::get_summary_function(CallExpr
*call
)
937 FunctionDecl
*decl
= call
->getDirectCallee();
941 if (!options
->pencil
)
944 specific_attr_iterator
<AnnotateAttr
> begin
, end
, i
;
945 begin
= decl
->specific_attr_begin
<AnnotateAttr
>();
946 end
= decl
->specific_attr_end
<AnnotateAttr
>();
947 for (i
= begin
; i
!= end
; ++i
) {
948 string attr
= (*i
)->getAnnotation().str();
950 const char prefix
[] = "pencil_access(";
951 size_t start
= attr
.find(prefix
);
952 if (start
== string::npos
)
954 start
+= strlen(prefix
);
955 string name
= attr
.substr(start
, attr
.find(')') - start
);
957 return find_decl_from_name(call
, name
);
963 /* Is "name" the name of an assume statement?
964 * "pencil" indicates whether pencil builtins and pragmas should be supported.
965 * "__builtin_assume" is always accepted.
966 * If "pencil" is set, then "__pencil_assume" is also accepted.
968 static bool is_assume(int pencil
, const string
&name
)
970 if (name
== "__builtin_assume")
972 return pencil
&& name
== "__pencil_assume";
975 /* Construct a pet_expr representing a function call.
977 * In the special case of a "call" to __builtin_assume or __pencil_assume,
978 * construct an assume expression instead.
980 * In the case of a "call" to __pencil_kill, the arguments
981 * are neither read nor written (only killed), so there
982 * is no need to check for writes to these arguments.
984 * __pencil_assume and __pencil_kill are only recognized
985 * when the pencil option is set.
987 __isl_give pet_expr
*PetScan::extract_expr(CallExpr
*expr
)
989 pet_expr
*res
= NULL
;
995 fd
= expr
->getDirectCallee();
1001 name
= fd
->getDeclName().getAsString();
1002 n_arg
= expr
->getNumArgs();
1004 if (n_arg
== 1 && is_assume(options
->pencil
, name
))
1005 return extract_assume(expr
->getArg(0));
1006 is_kill
= options
->pencil
&& name
== "__pencil_kill";
1008 res
= pet_expr_new_call(ctx
, name
.c_str(), n_arg
);
1012 for (unsigned i
= 0; i
< n_arg
; ++i
) {
1013 Expr
*arg
= expr
->getArg(i
);
1014 res
= pet_expr_set_arg(res
, i
,
1015 PetScan::extract_argument(fd
, i
, arg
, !is_kill
));
1018 fd
= get_summary_function(expr
);
1020 return pet_expr_free(res
);
1022 res
= set_summary(res
, fd
);
1027 /* Construct a pet_expr representing a (C style) cast.
1029 __isl_give pet_expr
*PetScan::extract_expr(CStyleCastExpr
*expr
)
1034 arg
= extract_expr(expr
->getSubExpr());
1038 type
= expr
->getTypeAsWritten();
1039 return pet_expr_new_cast(type
.getAsString().c_str(), arg
);
1042 /* Construct a pet_expr representing an integer.
1044 __isl_give pet_expr
*PetScan::extract_expr(IntegerLiteral
*expr
)
1046 return pet_expr_new_int(extract_int(expr
));
1049 /* Construct a pet_expr representing the integer enum constant "ecd".
1051 __isl_give pet_expr
*PetScan::extract_expr(EnumConstantDecl
*ecd
)
1054 const llvm::APSInt
&init
= ecd
->getInitVal();
1055 v
= ::extract_int(ctx
, init
.isSigned(), init
);
1056 return pet_expr_new_int(v
);
1059 /* Try and construct a pet_expr representing "expr".
1061 __isl_give pet_expr
*PetScan::extract_expr(Expr
*expr
)
1063 switch (expr
->getStmtClass()) {
1064 case Stmt::UnaryOperatorClass
:
1065 return extract_expr(cast
<UnaryOperator
>(expr
));
1066 case Stmt::CompoundAssignOperatorClass
:
1067 case Stmt::BinaryOperatorClass
:
1068 return extract_expr(cast
<BinaryOperator
>(expr
));
1069 case Stmt::ImplicitCastExprClass
:
1070 return extract_expr(cast
<ImplicitCastExpr
>(expr
));
1071 case Stmt::ArraySubscriptExprClass
:
1072 case Stmt::DeclRefExprClass
:
1073 case Stmt::MemberExprClass
:
1074 return extract_access_expr(expr
);
1075 case Stmt::IntegerLiteralClass
:
1076 return extract_expr(cast
<IntegerLiteral
>(expr
));
1077 case Stmt::FloatingLiteralClass
:
1078 return extract_expr(cast
<FloatingLiteral
>(expr
));
1079 case Stmt::ParenExprClass
:
1080 return extract_expr(cast
<ParenExpr
>(expr
));
1081 case Stmt::ConditionalOperatorClass
:
1082 return extract_expr(cast
<ConditionalOperator
>(expr
));
1083 case Stmt::CallExprClass
:
1084 return extract_expr(cast
<CallExpr
>(expr
));
1085 case Stmt::CStyleCastExprClass
:
1086 return extract_expr(cast
<CStyleCastExpr
>(expr
));
1093 /* Check if the given initialization statement is an assignment.
1094 * If so, return that assignment. Otherwise return NULL.
1096 BinaryOperator
*PetScan::initialization_assignment(Stmt
*init
)
1098 BinaryOperator
*ass
;
1100 if (init
->getStmtClass() != Stmt::BinaryOperatorClass
)
1103 ass
= cast
<BinaryOperator
>(init
);
1104 if (ass
->getOpcode() != BO_Assign
)
1110 /* Check if the given initialization statement is a declaration
1111 * of a single variable.
1112 * If so, return that declaration. Otherwise return NULL.
1114 Decl
*PetScan::initialization_declaration(Stmt
*init
)
1118 if (init
->getStmtClass() != Stmt::DeclStmtClass
)
1121 decl
= cast
<DeclStmt
>(init
);
1123 if (!decl
->isSingleDecl())
1126 return decl
->getSingleDecl();
1129 /* Given the assignment operator in the initialization of a for loop,
1130 * extract the induction variable, i.e., the (integer)variable being
1133 ValueDecl
*PetScan::extract_induction_variable(BinaryOperator
*init
)
1140 lhs
= init
->getLHS();
1141 if (lhs
->getStmtClass() != Stmt::DeclRefExprClass
) {
1146 ref
= cast
<DeclRefExpr
>(lhs
);
1147 decl
= ref
->getDecl();
1148 type
= decl
->getType().getTypePtr();
1150 if (!type
->isIntegerType()) {
1158 /* Given the initialization statement of a for loop and the single
1159 * declaration in this initialization statement,
1160 * extract the induction variable, i.e., the (integer) variable being
1163 VarDecl
*PetScan::extract_induction_variable(Stmt
*init
, Decl
*decl
)
1167 vd
= cast
<VarDecl
>(decl
);
1169 const QualType type
= vd
->getType();
1170 if (!type
->isIntegerType()) {
1175 if (!vd
->getInit()) {
1183 /* Check that op is of the form iv++ or iv--.
1184 * Return a pet_expr representing "1" or "-1" accordingly.
1186 __isl_give pet_expr
*PetScan::extract_unary_increment(
1187 clang::UnaryOperator
*op
, clang::ValueDecl
*iv
)
1193 if (!op
->isIncrementDecrementOp()) {
1198 sub
= op
->getSubExpr();
1199 if (sub
->getStmtClass() != Stmt::DeclRefExprClass
) {
1204 ref
= cast
<DeclRefExpr
>(sub
);
1205 if (ref
->getDecl() != iv
) {
1210 if (op
->isIncrementOp())
1211 v
= isl_val_one(ctx
);
1213 v
= isl_val_negone(ctx
);
1215 return pet_expr_new_int(v
);
1218 /* Check if op is of the form
1222 * and return the increment "expr - iv" as a pet_expr.
1224 __isl_give pet_expr
*PetScan::extract_binary_increment(BinaryOperator
*op
,
1225 clang::ValueDecl
*iv
)
1230 pet_expr
*expr
, *expr_iv
;
1232 if (op
->getOpcode() != BO_Assign
) {
1238 if (lhs
->getStmtClass() != Stmt::DeclRefExprClass
) {
1243 ref
= cast
<DeclRefExpr
>(lhs
);
1244 if (ref
->getDecl() != iv
) {
1249 expr
= extract_expr(op
->getRHS());
1250 expr_iv
= extract_expr(lhs
);
1252 type_size
= pet_clang_get_type_size(iv
->getType(), ast_context
);
1253 return pet_expr_new_binary(type_size
, pet_op_sub
, expr
, expr_iv
);
1256 /* Check that op is of the form iv += cst or iv -= cst
1257 * and return a pet_expr corresponding to cst or -cst accordingly.
1259 __isl_give pet_expr
*PetScan::extract_compound_increment(
1260 CompoundAssignOperator
*op
, clang::ValueDecl
*iv
)
1266 BinaryOperatorKind opcode
;
1268 opcode
= op
->getOpcode();
1269 if (opcode
!= BO_AddAssign
&& opcode
!= BO_SubAssign
) {
1273 if (opcode
== BO_SubAssign
)
1277 if (lhs
->getStmtClass() != Stmt::DeclRefExprClass
) {
1282 ref
= cast
<DeclRefExpr
>(lhs
);
1283 if (ref
->getDecl() != iv
) {
1288 expr
= extract_expr(op
->getRHS());
1291 type_size
= pet_clang_get_type_size(op
->getType(), ast_context
);
1292 expr
= pet_expr_new_unary(type_size
, pet_op_minus
, expr
);
1298 /* Check that the increment of the given for loop increments
1299 * (or decrements) the induction variable "iv" and return
1300 * the increment as a pet_expr if successful.
1302 __isl_give pet_expr
*PetScan::extract_increment(clang::ForStmt
*stmt
,
1305 Stmt
*inc
= stmt
->getInc();
1308 report_missing_increment(stmt
);
1312 if (inc
->getStmtClass() == Stmt::UnaryOperatorClass
)
1313 return extract_unary_increment(cast
<UnaryOperator
>(inc
), iv
);
1314 if (inc
->getStmtClass() == Stmt::CompoundAssignOperatorClass
)
1315 return extract_compound_increment(
1316 cast
<CompoundAssignOperator
>(inc
), iv
);
1317 if (inc
->getStmtClass() == Stmt::BinaryOperatorClass
)
1318 return extract_binary_increment(cast
<BinaryOperator
>(inc
), iv
);
1324 /* Construct a pet_tree for a while loop.
1326 * If we were only able to extract part of the body, then simply
1329 __isl_give pet_tree
*PetScan::extract(WhileStmt
*stmt
)
1334 tree
= extract(stmt
->getBody());
1337 pe_cond
= extract_expr(stmt
->getCond());
1338 tree
= pet_tree_new_while(pe_cond
, tree
);
1343 /* Construct a pet_tree for a for statement.
1344 * The for loop is required to be of one of the following forms
1346 * for (i = init; condition; ++i)
1347 * for (i = init; condition; --i)
1348 * for (i = init; condition; i += constant)
1349 * for (i = init; condition; i -= constant)
1351 * We extract a pet_tree for the body and then include it in a pet_tree
1352 * of type pet_tree_for.
1354 * As a special case, we also allow a for loop of the form
1358 * in which case we return a pet_tree of type pet_tree_infinite_loop.
1360 * If we were only able to extract part of the body, then simply
1363 __isl_give pet_tree
*PetScan::extract_for(ForStmt
*stmt
)
1365 BinaryOperator
*ass
;
1373 pet_expr
*pe_init
, *pe_inc
, *pe_iv
, *pe_cond
;
1375 independent
= is_current_stmt_marked_independent();
1377 if (!stmt
->getInit() && !stmt
->getCond() && !stmt
->getInc()) {
1378 tree
= extract(stmt
->getBody());
1381 tree
= pet_tree_new_infinite_loop(tree
);
1385 init
= stmt
->getInit();
1390 if ((ass
= initialization_assignment(init
)) != NULL
) {
1391 iv
= extract_induction_variable(ass
);
1394 rhs
= ass
->getRHS();
1395 } else if ((decl
= initialization_declaration(init
)) != NULL
) {
1396 VarDecl
*var
= extract_induction_variable(init
, decl
);
1400 rhs
= var
->getInit();
1402 unsupported(stmt
->getInit());
1406 declared
= !initialization_assignment(stmt
->getInit());
1407 tree
= extract(stmt
->getBody());
1410 pe_iv
= extract_access_expr(iv
);
1411 pe_iv
= mark_write(pe_iv
);
1412 pe_init
= extract_expr(rhs
);
1413 if (!stmt
->getCond())
1414 pe_cond
= pet_expr_new_int(isl_val_one(ctx
));
1416 pe_cond
= extract_expr(stmt
->getCond());
1417 pe_inc
= extract_increment(stmt
, iv
);
1418 tree
= pet_tree_new_for(independent
, declared
, pe_iv
, pe_init
, pe_cond
,
1423 /* Store the names of the variables declared in decl_context
1424 * in the set declared_names. Make sure to only do this once by
1425 * setting declared_names_collected.
1427 void PetScan::collect_declared_names()
1429 DeclContext
*DC
= decl_context
;
1430 DeclContext::decl_iterator it
;
1432 if (declared_names_collected
)
1435 for (it
= DC
->decls_begin(); it
!= DC
->decls_end(); ++it
) {
1439 if (!isa
<NamedDecl
>(D
))
1441 named
= cast
<NamedDecl
>(D
);
1442 declared_names
.insert(named
->getName().str());
1445 declared_names_collected
= true;
1448 /* Add the names in "names" that are not also in this->declared_names
1449 * to this->used_names.
1450 * It is up to the caller to make sure that declared_names has been
1451 * populated, if needed.
1453 void PetScan::add_new_used_names(const std::set
<std::string
> &names
)
1455 std::set
<std::string
>::const_iterator it
;
1457 for (it
= names
.begin(); it
!= names
.end(); ++it
) {
1458 if (declared_names
.find(*it
) != declared_names
.end())
1460 used_names
.insert(*it
);
1464 /* Is the name "name" used in any declaration other than "decl"?
1466 * If the name was found to be in use before, the consider it to be in use.
1467 * Otherwise, check the DeclContext of the function containing the scop
1468 * as well as all ancestors of this DeclContext for declarations
1469 * other than "decl" that declare something called "name".
1471 bool PetScan::name_in_use(const string
&name
, Decl
*decl
)
1474 DeclContext::decl_iterator it
;
1476 if (used_names
.find(name
) != used_names
.end())
1479 for (DC
= decl_context
; DC
; DC
= DC
->getParent()) {
1480 for (it
= DC
->decls_begin(); it
!= DC
->decls_end(); ++it
) {
1486 if (!isa
<NamedDecl
>(D
))
1488 named
= cast
<NamedDecl
>(D
);
1489 if (named
->getName().str() == name
)
1497 /* Generate a new name based on "name" that is not in use.
1498 * Do so by adding a suffix _i, with i an integer.
1500 string
PetScan::generate_new_name(const string
&name
)
1505 std::ostringstream oss
;
1506 oss
<< name
<< "_" << n_rename
++;
1507 new_name
= oss
.str();
1508 } while (name_in_use(new_name
, NULL
));
1513 /* Try and construct a pet_tree corresponding to a compound statement.
1515 * "skip_declarations" is set if we should skip initial declarations
1516 * in the children of the compound statements.
1518 * Collect a new set of declarations for the current compound statement.
1519 * If any of the names in these declarations is also used by another
1520 * declaration reachable from the current function, then rename it
1521 * to a name that is not already in use.
1522 * In particular, keep track of the old and new names in a pet_substituter
1523 * and apply the substitutions to the pet_tree corresponding to the
1524 * compound statement.
1526 __isl_give pet_tree
*PetScan::extract(CompoundStmt
*stmt
,
1527 bool skip_declarations
)
1530 std::vector
<VarDecl
*> saved_declarations
;
1531 std::vector
<VarDecl
*>::iterator it
;
1532 pet_substituter substituter
;
1534 saved_declarations
= declarations
;
1535 declarations
.clear();
1536 tree
= extract(stmt
->children(), true, skip_declarations
, stmt
);
1537 for (it
= declarations
.begin(); it
!= declarations
.end(); ++it
) {
1540 VarDecl
*decl
= *it
;
1541 string name
= decl
->getName().str();
1542 bool in_use
= name_in_use(name
, decl
);
1544 used_names
.insert(name
);
1548 name
= generate_new_name(name
);
1549 id
= pet_id_from_name_and_decl(ctx
, name
.c_str(), decl
);
1550 expr
= pet_expr_access_from_id(id
, ast_context
);
1551 id
= pet_id_from_decl(ctx
, decl
);
1552 substituter
.add_sub(id
, expr
);
1553 used_names
.insert(name
);
1555 tree
= substituter
.substitute(tree
);
1556 declarations
= saved_declarations
;
1561 /* Return the file offset of the expansion location of "Loc".
1563 static unsigned getExpansionOffset(SourceManager
&SM
, SourceLocation Loc
)
1565 return SM
.getFileOffset(SM
.getExpansionLoc(Loc
));
1568 #ifdef HAVE_FINDLOCATIONAFTERTOKEN
1570 /* Return a SourceLocation for the location after the first semicolon
1571 * after "loc". If Lexer::findLocationAfterToken is available, we simply
1572 * call it and also skip trailing spaces and newline.
1574 static SourceLocation
location_after_semi(SourceLocation loc
, SourceManager
&SM
,
1575 const LangOptions
&LO
)
1577 return Lexer::findLocationAfterToken(loc
, tok::semi
, SM
, LO
, true);
1582 /* Return a SourceLocation for the location after the first semicolon
1583 * after "loc". If Lexer::findLocationAfterToken is not available,
1584 * we look in the underlying character data for the first semicolon.
1586 static SourceLocation
location_after_semi(SourceLocation loc
, SourceManager
&SM
,
1587 const LangOptions
&LO
)
1590 const char *s
= SM
.getCharacterData(loc
);
1592 semi
= strchr(s
, ';');
1594 return SourceLocation();
1595 return loc
.getFileLocWithOffset(semi
+ 1 - s
);
1600 /* If the token at "loc" is the first token on the line, then return
1601 * a location referring to the start of the line and set *indent
1602 * to the indentation of "loc"
1603 * Otherwise, return "loc" and set *indent to "".
1605 * This function is used to extend a scop to the start of the line
1606 * if the first token of the scop is also the first token on the line.
1608 * We look for the first token on the line. If its location is equal to "loc",
1609 * then the latter is the location of the first token on the line.
1611 static SourceLocation
move_to_start_of_line_if_first_token(SourceLocation loc
,
1612 SourceManager
&SM
, const LangOptions
&LO
, char **indent
)
1614 std::pair
<FileID
, unsigned> file_offset_pair
;
1615 llvm::StringRef file
;
1618 SourceLocation token_loc
, line_loc
;
1622 loc
= SM
.getExpansionLoc(loc
);
1623 col
= SM
.getExpansionColumnNumber(loc
);
1624 line_loc
= loc
.getLocWithOffset(1 - col
);
1625 file_offset_pair
= SM
.getDecomposedLoc(line_loc
);
1626 file
= SM
.getBufferData(file_offset_pair
.first
, NULL
);
1627 pos
= file
.data() + file_offset_pair
.second
;
1629 Lexer
lexer(SM
.getLocForStartOfFile(file_offset_pair
.first
), LO
,
1630 file
.begin(), pos
, file
.end());
1631 lexer
.LexFromRawLexer(tok
);
1632 token_loc
= tok
.getLocation();
1634 s
= SM
.getCharacterData(line_loc
);
1635 *indent
= strndup(s
, token_loc
== loc
? col
- 1 : 0);
1637 if (token_loc
== loc
)
1643 /* Construct a pet_loc corresponding to the region covered by "range".
1644 * If "skip_semi" is set, then we assume "range" is followed by
1645 * a semicolon and also include this semicolon.
1647 __isl_give pet_loc
*PetScan::construct_pet_loc(SourceRange range
,
1650 SourceLocation loc
= range
.getBegin();
1651 SourceManager
&SM
= PP
.getSourceManager();
1652 const LangOptions
&LO
= PP
.getLangOpts();
1653 int line
= PP
.getSourceManager().getExpansionLineNumber(loc
);
1654 unsigned start
, end
;
1657 loc
= move_to_start_of_line_if_first_token(loc
, SM
, LO
, &indent
);
1658 start
= getExpansionOffset(SM
, loc
);
1659 loc
= range
.getEnd();
1661 loc
= location_after_semi(loc
, SM
, LO
);
1663 loc
= PP
.getLocForEndOfToken(loc
);
1664 end
= getExpansionOffset(SM
, loc
);
1666 return pet_loc_alloc(ctx
, start
, end
, line
, indent
);
1669 /* Convert a top-level pet_expr to an expression pet_tree.
1671 __isl_give pet_tree
*PetScan::extract(__isl_take pet_expr
*expr
,
1672 SourceRange range
, bool skip_semi
)
1677 tree
= pet_tree_new_expr(expr
);
1678 loc
= construct_pet_loc(range
, skip_semi
);
1679 tree
= pet_tree_set_loc(tree
, loc
);
1684 /* Construct a pet_tree for an if statement.
1686 __isl_give pet_tree
*PetScan::extract(IfStmt
*stmt
)
1689 pet_tree
*tree
, *tree_else
;
1691 pe_cond
= extract_expr(stmt
->getCond());
1692 tree
= extract(stmt
->getThen());
1693 if (stmt
->getElse()) {
1694 tree_else
= extract(stmt
->getElse());
1695 if (options
->autodetect
) {
1696 if (tree
&& !tree_else
) {
1698 pet_expr_free(pe_cond
);
1701 if (!tree
&& tree_else
) {
1703 pet_expr_free(pe_cond
);
1707 tree
= pet_tree_new_if_else(pe_cond
, tree
, tree_else
);
1709 tree
= pet_tree_new_if(pe_cond
, tree
);
1713 /* Try and construct a pet_tree for a label statement.
1715 __isl_give pet_tree
*PetScan::extract(LabelStmt
*stmt
)
1720 label
= isl_id_alloc(ctx
, stmt
->getName(), NULL
);
1722 tree
= extract(stmt
->getSubStmt());
1723 tree
= pet_tree_set_label(tree
, label
);
1727 /* Update the location of "tree" to include the source range of "stmt".
1729 * Actually, we create a new location based on the source range of "stmt" and
1730 * then extend this new location to include the region of the original location.
1731 * This ensures that the line number of the final location refers to "stmt".
1733 __isl_give pet_tree
*PetScan::update_loc(__isl_take pet_tree
*tree
, Stmt
*stmt
)
1735 pet_loc
*loc
, *tree_loc
;
1737 tree_loc
= pet_tree_get_loc(tree
);
1738 loc
= construct_pet_loc(stmt
->getSourceRange(), false);
1739 loc
= pet_loc_update_start_end_from_loc(loc
, tree_loc
);
1740 pet_loc_free(tree_loc
);
1742 tree
= pet_tree_set_loc(tree
, loc
);
1746 /* Is "expr" of a type that can be converted to an access expression?
1748 static bool is_access_expr_type(Expr
*expr
)
1750 switch (expr
->getStmtClass()) {
1751 case Stmt::ArraySubscriptExprClass
:
1752 case Stmt::DeclRefExprClass
:
1753 case Stmt::MemberExprClass
:
1760 /* Tell the pet_inliner "inliner" about the formal arguments
1761 * in "fd" and the corresponding actual arguments in "call".
1762 * Return 0 if this was successful and -1 otherwise.
1764 * Any pointer argument is treated as an array.
1765 * The other arguments are treated as scalars.
1767 * In case of scalars, there is no restriction on the actual argument.
1768 * This actual argument is assigned to a variable with a name
1769 * that is derived from the name of the corresponding formal argument,
1770 * but made not to conflict with any variable names that are
1773 * In case of arrays, the actual argument needs to be an expression
1774 * of a type that can be converted to an access expression or the address
1775 * of such an expression, ignoring implicit and redundant casts.
1777 int PetScan::set_inliner_arguments(pet_inliner
&inliner
, CallExpr
*call
,
1782 n
= fd
->getNumParams();
1783 for (unsigned i
= 0; i
< n
; ++i
) {
1784 ParmVarDecl
*parm
= fd
->getParamDecl(i
);
1785 QualType type
= parm
->getType();
1790 arg
= call
->getArg(i
);
1791 if (pet_clang_array_depth(type
) == 0) {
1792 string name
= parm
->getName().str();
1793 if (name_in_use(name
, NULL
))
1794 name
= generate_new_name(name
);
1795 used_names
.insert(name
);
1796 inliner
.add_scalar_arg(parm
, name
, extract_expr(arg
));
1799 arg
= pet_clang_strip_casts(arg
);
1800 sub
= extract_addr_of_arg(arg
);
1803 arg
= pet_clang_strip_casts(sub
);
1805 if (!is_access_expr_type(arg
)) {
1806 report_unsupported_inline_function_argument(arg
);
1809 expr
= extract_access_expr(arg
);
1812 inliner
.add_array_arg(parm
, expr
, is_addr
);
1818 /* Internal data structure for PetScan::substitute_array_sizes.
1819 * ps is the PetScan on which the method was called.
1820 * substituter is the substituter that is used to substitute variables
1821 * in the size expressions.
1823 struct pet_substitute_array_sizes_data
{
1825 pet_substituter
*substituter
;
1829 static int substitute_array_size(__isl_keep pet_tree
*tree
, void *user
);
1832 /* If "tree" is a declaration, then perform the substitutions
1833 * in data->substituter on its size expression and store the result
1834 * in the size expression cache of data->ps such that the modified expression
1835 * will be used in subsequent calls to get_array_size.
1837 static int substitute_array_size(__isl_keep pet_tree
*tree
, void *user
)
1839 struct pet_substitute_array_sizes_data
*data
;
1841 pet_expr
*var
, *size
;
1843 if (!pet_tree_is_decl(tree
))
1846 data
= (struct pet_substitute_array_sizes_data
*) user
;
1847 var
= pet_tree_decl_get_var(tree
);
1848 id
= pet_expr_access_get_id(var
);
1851 size
= data
->ps
->get_array_size(id
);
1852 size
= data
->substituter
->substitute(size
);
1853 data
->ps
->set_array_size(id
, size
);
1858 /* Perform the substitutions in "substituter" on all the arrays declared
1859 * inside "tree" and store the results in the size expression cache
1860 * such that the modified expressions will be used in subsequent calls
1861 * to get_array_size.
1863 int PetScan::substitute_array_sizes(__isl_keep pet_tree
*tree
,
1864 pet_substituter
*substituter
)
1866 struct pet_substitute_array_sizes_data data
= { this, substituter
};
1868 return pet_tree_foreach_sub_tree(tree
, &substitute_array_size
, &data
);
1871 /* Try and construct a pet_tree from the body of "fd" using the actual
1872 * arguments in "call" in place of the formal arguments.
1873 * "fd" is assumed to point to the declaration with a function body.
1874 * In particular, construct a block that consists of assignments
1875 * of (parts of) the actual arguments to temporary variables
1876 * followed by the inlined function body with the formal arguments
1877 * replaced by (expressions containing) these temporary variables.
1879 * The actual inlining is taken care of by the pet_inliner object.
1880 * This function merely calls set_inliner_arguments to tell
1881 * the pet_inliner about the actual arguments, extracts a pet_tree
1882 * from the body of the called function and then passes this pet_tree
1883 * to the pet_inliner.
1884 * The substitutions performed by the inliner are also applied
1885 * to the size expressions of the arrays declared in the inlined
1886 * function. These size expressions are not stored in the tree
1887 * itself, but rather in the size expression cache.
1889 * During the extraction of the function body, all variables names
1890 * that are declared in the calling function as well all variable
1891 * names that are known to be in use are considered to be in use
1892 * in the called function to ensure that there is no naming conflict.
1893 * Similarly, the additional names that are in use in the called function
1894 * are considered to be in use in the calling function as well.
1896 * The location of the pet_tree is reset to the call site to ensure
1897 * that the extent of the scop does not include the body of the called
1900 __isl_give pet_tree
*PetScan::extract_inlined_call(CallExpr
*call
,
1903 int save_autodetect
;
1906 pet_inliner
inliner(ctx
, n_arg
, ast_context
);
1908 if (set_inliner_arguments(inliner
, call
, fd
) < 0)
1911 save_autodetect
= options
->autodetect
;
1912 options
->autodetect
= 0;
1913 PetScan
body_scan(PP
, ast_context
, fd
, loc
, options
,
1914 isl_union_map_copy(value_bounds
), independent
);
1915 collect_declared_names();
1916 body_scan
.add_new_used_names(declared_names
);
1917 body_scan
.add_new_used_names(used_names
);
1918 tree
= body_scan
.extract(fd
->getBody(), false);
1919 add_new_used_names(body_scan
.used_names
);
1920 options
->autodetect
= save_autodetect
;
1922 tree_loc
= construct_pet_loc(call
->getSourceRange(), true);
1923 tree
= pet_tree_set_loc(tree
, tree_loc
);
1925 substitute_array_sizes(tree
, &inliner
);
1927 return inliner
.inline_tree(tree
);
1930 /* Try and construct a pet_tree corresponding
1931 * to the expression statement "stmt".
1933 * If the outer expression is a function call and if the corresponding
1934 * function body is marked "inline", then return a pet_tree
1935 * corresponding to the inlined function.
1937 __isl_give pet_tree
*PetScan::extract_expr_stmt(Stmt
*stmt
)
1941 if (stmt
->getStmtClass() == Stmt::CallExprClass
) {
1942 CallExpr
*call
= cast
<CallExpr
>(stmt
);
1943 FunctionDecl
*fd
= call
->getDirectCallee();
1944 fd
= pet_clang_find_function_decl_with_body(fd
);
1945 if (fd
&& fd
->isInlineSpecified())
1946 return extract_inlined_call(call
, fd
);
1949 expr
= extract_expr(cast
<Expr
>(stmt
));
1950 return extract(expr
, stmt
->getSourceRange(), true);
1953 /* Try and construct a pet_tree corresponding to "stmt".
1955 * If "stmt" is a compound statement, then "skip_declarations"
1956 * indicates whether we should skip initial declarations in the
1957 * compound statement.
1959 * If the constructed pet_tree is not a (possibly) partial representation
1960 * of "stmt", we update start and end of the pet_scop to those of "stmt".
1961 * In particular, if skip_declarations is set, then we may have skipped
1962 * declarations inside "stmt" and so the pet_scop may not represent
1963 * the entire "stmt".
1964 * Note that this function may be called with "stmt" referring to the entire
1965 * body of the function, including the outer braces. In such cases,
1966 * skip_declarations will be set and the braces will not be taken into
1967 * account in tree->loc.
1969 __isl_give pet_tree
*PetScan::extract(Stmt
*stmt
, bool skip_declarations
)
1973 set_current_stmt(stmt
);
1975 if (isa
<Expr
>(stmt
))
1976 return extract_expr_stmt(cast
<Expr
>(stmt
));
1978 switch (stmt
->getStmtClass()) {
1979 case Stmt::WhileStmtClass
:
1980 tree
= extract(cast
<WhileStmt
>(stmt
));
1982 case Stmt::ForStmtClass
:
1983 tree
= extract_for(cast
<ForStmt
>(stmt
));
1985 case Stmt::IfStmtClass
:
1986 tree
= extract(cast
<IfStmt
>(stmt
));
1988 case Stmt::CompoundStmtClass
:
1989 tree
= extract(cast
<CompoundStmt
>(stmt
), skip_declarations
);
1991 case Stmt::LabelStmtClass
:
1992 tree
= extract(cast
<LabelStmt
>(stmt
));
1994 case Stmt::ContinueStmtClass
:
1995 tree
= pet_tree_new_continue(ctx
);
1997 case Stmt::BreakStmtClass
:
1998 tree
= pet_tree_new_break(ctx
);
2000 case Stmt::DeclStmtClass
:
2001 tree
= extract(cast
<DeclStmt
>(stmt
));
2003 case Stmt::NullStmtClass
:
2004 tree
= pet_tree_new_block(ctx
, 0, 0);
2007 report_unsupported_statement_type(stmt
);
2011 if (partial
|| skip_declarations
)
2014 return update_loc(tree
, stmt
);
2017 /* Given a sequence of statements "stmt_range" of which the first "n_decl"
2018 * are declarations and of which the remaining statements are represented
2019 * by "tree", try and extend "tree" to include the last sequence of
2020 * the initial declarations that can be completely extracted.
2022 * We start collecting the initial declarations and start over
2023 * whenever we come across a declaration that we cannot extract.
2024 * If we have been able to extract any declarations, then we
2025 * copy over the contents of "tree" at the end of the declarations.
2026 * Otherwise, we simply return the original "tree".
2028 __isl_give pet_tree
*PetScan::insert_initial_declarations(
2029 __isl_take pet_tree
*tree
, int n_decl
, StmtRange stmt_range
)
2037 n_stmt
= pet_tree_block_n_child(tree
);
2038 is_block
= pet_tree_block_get_block(tree
);
2039 res
= pet_tree_new_block(ctx
, is_block
, n_decl
+ n_stmt
);
2041 for (i
= stmt_range
.first
; n_decl
; ++i
, --n_decl
) {
2045 tree_i
= extract(child
);
2046 if (tree_i
&& !partial
) {
2047 res
= pet_tree_block_add_child(res
, tree_i
);
2050 pet_tree_free(tree_i
);
2052 if (pet_tree_block_n_child(res
) == 0)
2055 res
= pet_tree_new_block(ctx
, is_block
, n_decl
+ n_stmt
);
2058 if (pet_tree_block_n_child(res
) == 0) {
2063 for (j
= 0; j
< n_stmt
; ++j
) {
2066 tree_i
= pet_tree_block_get_child(tree
, j
);
2067 res
= pet_tree_block_add_child(res
, tree_i
);
2069 pet_tree_free(tree
);
2074 /* Try and construct a pet_tree corresponding to (part of)
2075 * a sequence of statements.
2077 * "block" is set if the sequence represents the children of
2078 * a compound statement.
2079 * "skip_declarations" is set if we should skip initial declarations
2080 * in the sequence of statements.
2081 * "parent" is the statement that has stmt_range as (some of) its children.
2083 * If autodetect is set, then we allow the extraction of only a subrange
2084 * of the sequence of statements. However, if there is at least one
2085 * kill and there is some subsequent statement for which we could not
2086 * construct a tree, then turn off the "block" property of the tree
2087 * such that no extra kill will be introduced at the end of the (partial)
2088 * block. If, on the other hand, the final range contains
2089 * no statements, then we discard the entire range.
2090 * If only a subrange of the sequence was extracted, but each statement
2091 * in the sequence was extracted completely, and if there are some
2092 * variable declarations in the sequence before or inside
2093 * the extracted subrange, then check if any of these variables are
2094 * not used after the extracted subrange. If so, add kills to these
2097 * If the entire range was extracted, apart from some initial declarations,
2098 * then we try and extend the range with the latest of those initial
2101 __isl_give pet_tree
*PetScan::extract(StmtRange stmt_range
, bool block
,
2102 bool skip_declarations
, Stmt
*parent
)
2106 bool has_kills
= false;
2107 bool partial_range
= false;
2108 bool outer_partial
= false;
2110 SourceManager
&SM
= PP
.getSourceManager();
2111 pet_killed_locals
kl(SM
);
2112 unsigned range_start
, range_end
;
2114 for (i
= stmt_range
.first
, j
= 0; i
!= stmt_range
.second
; ++i
, ++j
)
2117 tree
= pet_tree_new_block(ctx
, block
, j
);
2120 i
= stmt_range
.first
;
2121 if (skip_declarations
)
2122 for (; i
!= stmt_range
.second
; ++i
) {
2123 if ((*i
)->getStmtClass() != Stmt::DeclStmtClass
)
2125 if (options
->autodetect
)
2126 kl
.add_locals(cast
<DeclStmt
>(*i
));
2130 for (; i
!= stmt_range
.second
; ++i
) {
2134 tree_i
= extract(child
);
2135 if (pet_tree_block_n_child(tree
) != 0 && partial
) {
2136 pet_tree_free(tree_i
);
2139 if (child
->getStmtClass() == Stmt::DeclStmtClass
) {
2140 if (options
->autodetect
)
2141 kl
.add_locals(cast
<DeclStmt
>(child
));
2142 if (tree_i
&& block
)
2145 if (options
->autodetect
) {
2147 range_end
= getExpansionOffset(SM
,
2148 child
->getLocEnd());
2149 if (pet_tree_block_n_child(tree
) == 0)
2150 range_start
= getExpansionOffset(SM
,
2151 child
->getLocStart());
2152 tree
= pet_tree_block_add_child(tree
, tree_i
);
2154 partial_range
= true;
2156 if (pet_tree_block_n_child(tree
) != 0 && !tree_i
)
2157 outer_partial
= partial
= true;
2159 tree
= pet_tree_block_add_child(tree
, tree_i
);
2162 if (partial
|| !tree
)
2171 tree
= pet_tree_block_set_block(tree
, 0);
2172 if (outer_partial
) {
2173 kl
.remove_accessed_after(parent
,
2174 range_start
, range_end
);
2175 tree
= add_kills(tree
, kl
.locals
);
2177 } else if (partial_range
) {
2178 if (pet_tree_block_n_child(tree
) == 0) {
2179 pet_tree_free(tree
);
2183 } else if (skip
> 0)
2184 tree
= insert_initial_declarations(tree
, skip
, stmt_range
);
2190 static __isl_give pet_expr
*get_array_size(__isl_keep pet_expr
*access
,
2192 static struct pet_array
*extract_array(__isl_keep pet_expr
*access
,
2193 __isl_keep pet_context
*pc
, void *user
);
2196 /* Construct a pet_expr that holds the sizes of the array accessed
2198 * This function is used as a callback to pet_context_add_parameters,
2199 * which is also passed a pointer to the PetScan object.
2201 static __isl_give pet_expr
*get_array_size(__isl_keep pet_expr
*access
,
2204 PetScan
*ps
= (PetScan
*) user
;
2208 id
= pet_expr_access_get_id(access
);
2209 size
= ps
->get_array_size(id
);
2215 /* Construct and return a pet_array corresponding to the variable
2216 * accessed by "access".
2217 * This function is used as a callback to pet_scop_from_pet_tree,
2218 * which is also passed a pointer to the PetScan object.
2220 static struct pet_array
*extract_array(__isl_keep pet_expr
*access
,
2221 __isl_keep pet_context
*pc
, void *user
)
2223 PetScan
*ps
= (PetScan
*) user
;
2227 id
= pet_expr_access_get_id(access
);
2228 array
= ps
->extract_array(id
, NULL
, pc
);
2234 /* Extract a function summary from the body of "fd".
2236 * We extract a scop from the function body in a context with as
2237 * parameters the integer arguments of the function.
2238 * We turn off autodetection (in case it was set) to ensure that
2239 * the entire function body is considered.
2240 * We then collect the accessed array elements and attach them
2241 * to the corresponding array arguments, taking into account
2242 * that the function body may access members of array elements.
2244 * The reason for representing the integer arguments as parameters in
2245 * the context is that if we were to instead start with a context
2246 * with the function arguments as initial dimensions, then we would not
2247 * be able to refer to them from the array extents, without turning
2248 * array extents into maps.
2250 * The result is stored in the summary_cache cache so that we can reuse
2251 * it if this method gets called on the same function again later on.
2253 __isl_give pet_function_summary
*PetScan::get_summary(FunctionDecl
*fd
)
2259 pet_function_summary
*summary
;
2262 int save_autodetect
;
2263 struct pet_scop
*scop
;
2265 isl_union_set
*may_read
, *may_write
, *must_write
;
2266 isl_union_map
*to_inner
;
2268 if (summary_cache
.find(fd
) != summary_cache
.end())
2269 return pet_function_summary_copy(summary_cache
[fd
]);
2271 space
= isl_space_set_alloc(ctx
, 0, 0);
2273 n
= fd
->getNumParams();
2274 summary
= pet_function_summary_alloc(ctx
, n
);
2275 for (unsigned i
= 0; i
< n
; ++i
) {
2276 ParmVarDecl
*parm
= fd
->getParamDecl(i
);
2277 QualType type
= parm
->getType();
2280 if (!type
->isIntegerType())
2282 id
= pet_id_from_decl(ctx
, parm
);
2283 space
= isl_space_insert_dims(space
, isl_dim_param
, 0, 1);
2284 space
= isl_space_set_dim_id(space
, isl_dim_param
, 0,
2286 summary
= pet_function_summary_set_int(summary
, i
, id
);
2289 save_autodetect
= options
->autodetect
;
2290 options
->autodetect
= 0;
2291 PetScan
body_scan(PP
, ast_context
, fd
, loc
, options
,
2292 isl_union_map_copy(value_bounds
), independent
);
2294 tree
= body_scan
.extract(fd
->getBody(), false);
2296 domain
= isl_set_universe(space
);
2297 pc
= pet_context_alloc(domain
);
2298 pc
= pet_context_add_parameters(pc
, tree
,
2299 &::get_array_size
, &body_scan
);
2300 int_size
= size_in_bytes(ast_context
, ast_context
.IntTy
);
2301 scop
= pet_scop_from_pet_tree(tree
, int_size
,
2302 &::extract_array
, &body_scan
, pc
);
2303 scop
= scan_arrays(scop
, pc
);
2304 may_read
= isl_union_map_range(pet_scop_get_may_reads(scop
));
2305 may_write
= isl_union_map_range(pet_scop_get_may_writes(scop
));
2306 must_write
= isl_union_map_range(pet_scop_get_must_writes(scop
));
2307 to_inner
= pet_scop_compute_outer_to_inner(scop
);
2308 pet_scop_free(scop
);
2310 for (unsigned i
= 0; i
< n
; ++i
) {
2311 ParmVarDecl
*parm
= fd
->getParamDecl(i
);
2312 QualType type
= parm
->getType();
2313 struct pet_array
*array
;
2315 isl_union_set
*data_set
;
2316 isl_union_set
*may_read_i
, *may_write_i
, *must_write_i
;
2318 if (pet_clang_array_depth(type
) == 0)
2321 array
= body_scan
.extract_array(parm
, NULL
, pc
);
2322 space
= array
? isl_set_get_space(array
->extent
) : NULL
;
2323 pet_array_free(array
);
2324 data_set
= isl_union_set_from_set(isl_set_universe(space
));
2325 data_set
= isl_union_set_apply(data_set
,
2326 isl_union_map_copy(to_inner
));
2327 may_read_i
= isl_union_set_intersect(
2328 isl_union_set_copy(may_read
),
2329 isl_union_set_copy(data_set
));
2330 may_write_i
= isl_union_set_intersect(
2331 isl_union_set_copy(may_write
),
2332 isl_union_set_copy(data_set
));
2333 must_write_i
= isl_union_set_intersect(
2334 isl_union_set_copy(must_write
), data_set
);
2335 summary
= pet_function_summary_set_array(summary
, i
,
2336 may_read_i
, may_write_i
, must_write_i
);
2339 isl_union_set_free(may_read
);
2340 isl_union_set_free(may_write
);
2341 isl_union_set_free(must_write
);
2342 isl_union_map_free(to_inner
);
2344 options
->autodetect
= save_autodetect
;
2345 pet_context_free(pc
);
2347 summary_cache
[fd
] = pet_function_summary_copy(summary
);
2352 /* If "fd" has a function body, then extract a function summary from
2353 * this body and attach it to the call expression "expr".
2355 * Even if a function body is available, "fd" itself may point
2356 * to a declaration without function body. We therefore first
2357 * replace it by the declaration that comes with a body (if any).
2359 __isl_give pet_expr
*PetScan::set_summary(__isl_take pet_expr
*expr
,
2362 pet_function_summary
*summary
;
2366 fd
= pet_clang_find_function_decl_with_body(fd
);
2370 summary
= get_summary(fd
);
2372 expr
= pet_expr_call_set_summary(expr
, summary
);
2377 /* Extract a pet_scop from "tree".
2379 * We simply call pet_scop_from_pet_tree with the appropriate arguments and
2380 * then add pet_arrays for all accessed arrays.
2381 * We populate the pet_context with assignments for all parameters used
2382 * inside "tree" or any of the size expressions for the arrays accessed
2383 * by "tree" so that they can be used in affine expressions.
2385 struct pet_scop
*PetScan::extract_scop(__isl_take pet_tree
*tree
)
2392 int_size
= size_in_bytes(ast_context
, ast_context
.IntTy
);
2394 domain
= isl_set_universe(isl_space_set_alloc(ctx
, 0, 0));
2395 pc
= pet_context_alloc(domain
);
2396 pc
= pet_context_add_parameters(pc
, tree
, &::get_array_size
, this);
2397 scop
= pet_scop_from_pet_tree(tree
, int_size
,
2398 &::extract_array
, this, pc
);
2399 scop
= scan_arrays(scop
, pc
);
2400 pet_context_free(pc
);
2405 /* Add a call to __pencil_kill to the end of "tree" that kills
2406 * all the variables in "locals" and return the result.
2408 * No location is added to the kill because the most natural
2409 * location would lie outside the scop. Attaching such a location
2410 * to this tree would extend the scope of the final result
2411 * to include the location.
2413 __isl_give pet_tree
*PetScan::add_kills(__isl_take pet_tree
*tree
,
2414 set
<ValueDecl
*> locals
)
2418 pet_tree
*kill
, *block
;
2419 set
<ValueDecl
*>::iterator it
;
2421 if (locals
.size() == 0)
2423 expr
= pet_expr_new_call(ctx
, "__pencil_kill", locals
.size());
2425 for (it
= locals
.begin(); it
!= locals
.end(); ++it
) {
2427 arg
= extract_access_expr(*it
);
2428 expr
= pet_expr_set_arg(expr
, i
++, arg
);
2430 kill
= pet_tree_new_expr(expr
);
2431 block
= pet_tree_new_block(ctx
, 0, 2);
2432 block
= pet_tree_block_add_child(block
, tree
);
2433 block
= pet_tree_block_add_child(block
, kill
);
2438 /* Check if the scop marked by the user is exactly this Stmt
2439 * or part of this Stmt.
2440 * If so, return a pet_scop corresponding to the marked region.
2441 * Otherwise, return NULL.
2443 * If the scop is not further nested inside a child of "stmt",
2444 * then check if there are any variable declarations before the scop
2445 * inside "stmt". If so, and if these variables are not used
2446 * after the scop, then add kills to the variables.
2448 * If the scop starts in the middle of one of the children, without
2449 * also ending in that child, then report an error.
2451 struct pet_scop
*PetScan::scan(Stmt
*stmt
)
2453 SourceManager
&SM
= PP
.getSourceManager();
2454 unsigned start_off
, end_off
;
2457 start_off
= getExpansionOffset(SM
, stmt
->getLocStart());
2458 end_off
= getExpansionOffset(SM
, stmt
->getLocEnd());
2460 if (start_off
> loc
.end
)
2462 if (end_off
< loc
.start
)
2465 if (start_off
>= loc
.start
&& end_off
<= loc
.end
)
2466 return extract_scop(extract(stmt
));
2468 pet_killed_locals
kl(SM
);
2470 for (start
= stmt
->child_begin(); start
!= stmt
->child_end(); ++start
) {
2471 Stmt
*child
= *start
;
2474 start_off
= getExpansionOffset(SM
, child
->getLocStart());
2475 end_off
= getExpansionOffset(SM
, child
->getLocEnd());
2476 if (start_off
< loc
.start
&& end_off
>= loc
.end
)
2478 if (start_off
>= loc
.start
)
2480 if (loc
.start
< end_off
) {
2481 report_unbalanced_pragmas(loc
.scop
, loc
.endscop
);
2484 if (isa
<DeclStmt
>(child
))
2485 kl
.add_locals(cast
<DeclStmt
>(child
));
2489 for (end
= start
; end
!= stmt
->child_end(); ++end
) {
2491 start_off
= SM
.getFileOffset(child
->getLocStart());
2492 if (start_off
>= loc
.end
)
2496 kl
.remove_accessed_after(stmt
, loc
.start
, loc
.end
);
2498 tree
= extract(StmtRange(start
, end
), false, false, stmt
);
2499 tree
= add_kills(tree
, kl
.locals
);
2500 return extract_scop(tree
);
2503 /* Set the size of index "pos" of "array" to "size".
2504 * In particular, add a constraint of the form
2508 * to array->extent and a constraint of the form
2512 * to array->context.
2514 * The domain of "size" is assumed to be zero-dimensional.
2516 static struct pet_array
*update_size(struct pet_array
*array
, int pos
,
2517 __isl_take isl_pw_aff
*size
)
2530 valid
= isl_set_params(isl_pw_aff_nonneg_set(isl_pw_aff_copy(size
)));
2531 array
->context
= isl_set_intersect(array
->context
, valid
);
2533 dim
= isl_set_get_space(array
->extent
);
2534 aff
= isl_aff_zero_on_domain(isl_local_space_from_space(dim
));
2535 aff
= isl_aff_add_coefficient_si(aff
, isl_dim_in
, pos
, 1);
2536 univ
= isl_set_universe(isl_aff_get_domain_space(aff
));
2537 index
= isl_pw_aff_alloc(univ
, aff
);
2539 size
= isl_pw_aff_add_dims(size
, isl_dim_in
,
2540 isl_set_dim(array
->extent
, isl_dim_set
));
2541 id
= isl_set_get_tuple_id(array
->extent
);
2542 size
= isl_pw_aff_set_tuple_id(size
, isl_dim_in
, id
);
2543 bound
= isl_pw_aff_lt_set(index
, size
);
2545 array
->extent
= isl_set_intersect(array
->extent
, bound
);
2547 if (!array
->context
|| !array
->extent
)
2548 return pet_array_free(array
);
2552 isl_pw_aff_free(size
);
2556 #ifdef HAVE_DECAYEDTYPE
2558 /* If "qt" is a decayed type, then set *decayed to true and
2559 * return the original type.
2561 static QualType
undecay(QualType qt
, bool *decayed
)
2563 const Type
*type
= qt
.getTypePtr();
2565 *decayed
= isa
<DecayedType
>(type
);
2567 qt
= cast
<DecayedType
>(type
)->getOriginalType();
2573 /* If "qt" is a decayed type, then set *decayed to true and
2574 * return the original type.
2575 * Since this version of clang does not define a DecayedType,
2576 * we cannot obtain the original type even if it had been decayed and
2577 * we set *decayed to false.
2579 static QualType
undecay(QualType qt
, bool *decayed
)
2587 /* Figure out the size of the array at position "pos" and all
2588 * subsequent positions from "qt" and update the corresponding
2589 * argument of "expr" accordingly.
2591 * The initial type (when pos is zero) may be a pointer type decayed
2592 * from an array type, if this initial type is the type of a function
2593 * argument. This only happens if the original array type has
2594 * a constant size in the outer dimension as otherwise we get
2595 * a VariableArrayType. Try and obtain this original type (if available) and
2596 * take the outer array size into account if it was marked static.
2598 __isl_give pet_expr
*PetScan::set_upper_bounds(__isl_take pet_expr
*expr
,
2599 QualType qt
, int pos
)
2601 const ArrayType
*atype
;
2603 bool decayed
= false;
2609 qt
= undecay(qt
, &decayed
);
2611 if (qt
->isPointerType()) {
2612 qt
= qt
->getPointeeType();
2613 return set_upper_bounds(expr
, qt
, pos
+ 1);
2615 if (!qt
->isArrayType())
2618 qt
= qt
->getCanonicalTypeInternal();
2619 atype
= cast
<ArrayType
>(qt
.getTypePtr());
2621 if (decayed
&& atype
->getSizeModifier() != ArrayType::Static
) {
2622 qt
= atype
->getElementType();
2623 return set_upper_bounds(expr
, qt
, pos
+ 1);
2626 if (qt
->isConstantArrayType()) {
2627 const ConstantArrayType
*ca
= cast
<ConstantArrayType
>(atype
);
2628 size
= extract_expr(ca
->getSize());
2629 expr
= pet_expr_set_arg(expr
, pos
, size
);
2630 } else if (qt
->isVariableArrayType()) {
2631 const VariableArrayType
*vla
= cast
<VariableArrayType
>(atype
);
2632 size
= extract_expr(vla
->getSizeExpr());
2633 expr
= pet_expr_set_arg(expr
, pos
, size
);
2636 qt
= atype
->getElementType();
2638 return set_upper_bounds(expr
, qt
, pos
+ 1);
2641 /* Construct a pet_expr that holds the sizes of the array represented by "id".
2642 * The returned expression is a call expression with as arguments
2643 * the sizes in each dimension. If we are unable to derive the size
2644 * in a given dimension, then the corresponding argument is set to infinity.
2645 * In fact, we initialize all arguments to infinity and then update
2646 * them if we are able to figure out the size.
2648 * The result is stored in the id_size cache so that it can be reused
2649 * if this method is called on the same array identifier later.
2650 * The result is also stored in the type_size cache in case
2651 * it gets called on a different array identifier with the same type.
2653 __isl_give pet_expr
*PetScan::get_array_size(__isl_keep isl_id
*id
)
2655 QualType qt
= pet_id_get_array_type(id
);
2657 pet_expr
*expr
, *inf
;
2658 const Type
*type
= qt
.getTypePtr();
2659 isl_maybe_pet_expr m
;
2661 m
= isl_id_to_pet_expr_try_get(id_size
, id
);
2662 if (m
.valid
< 0 || m
.valid
)
2664 if (type_size
.find(type
) != type_size
.end())
2665 return pet_expr_copy(type_size
[type
]);
2667 depth
= pet_clang_array_depth(qt
);
2668 inf
= pet_expr_new_int(isl_val_infty(ctx
));
2669 expr
= pet_expr_new_call(ctx
, "bounds", depth
);
2670 for (int i
= 0; i
< depth
; ++i
)
2671 expr
= pet_expr_set_arg(expr
, i
, pet_expr_copy(inf
));
2674 expr
= set_upper_bounds(expr
, qt
, 0);
2675 type_size
[type
] = pet_expr_copy(expr
);
2676 id_size
= isl_id_to_pet_expr_set(id_size
, isl_id_copy(id
),
2677 pet_expr_copy(expr
));
2682 /* Set the array size of the array identified by "id" to "size",
2683 * replacing any previously stored value.
2685 void PetScan::set_array_size(__isl_take isl_id
*id
, __isl_take pet_expr
*size
)
2687 id_size
= isl_id_to_pet_expr_set(id_size
, id
, size
);
2690 /* Does "expr" represent the "integer" infinity?
2692 static int is_infty(__isl_keep pet_expr
*expr
)
2697 if (pet_expr_get_type(expr
) != pet_expr_int
)
2699 v
= pet_expr_int_get_val(expr
);
2700 res
= isl_val_is_infty(v
);
2706 /* Figure out the dimensions of an array "array" and
2707 * update "array" accordingly.
2709 * We first construct a pet_expr that holds the sizes of the array
2710 * in each dimension. The resulting expression may containing
2711 * infinity values for dimension where we are unable to derive
2712 * a size expression.
2714 * The arguments of the size expression that have a value different from
2715 * infinity are then converted to an affine expression
2716 * within the context "pc" and incorporated into the size of "array".
2717 * If we are unable to convert a size expression to an affine expression or
2718 * if the size is not a (symbolic) constant,
2719 * then we leave the corresponding size of "array" untouched.
2721 struct pet_array
*PetScan::set_upper_bounds(struct pet_array
*array
,
2722 __isl_keep pet_context
*pc
)
2731 id
= isl_set_get_tuple_id(array
->extent
);
2732 expr
= get_array_size(id
);
2735 n
= pet_expr_get_n_arg(expr
);
2736 for (int i
= 0; i
< n
; ++i
) {
2740 arg
= pet_expr_get_arg(expr
, i
);
2741 if (!is_infty(arg
)) {
2744 size
= pet_expr_extract_affine(arg
, pc
);
2745 dim
= isl_pw_aff_dim(size
, isl_dim_in
);
2747 array
= pet_array_free(array
);
2748 else if (isl_pw_aff_involves_nan(size
) ||
2749 isl_pw_aff_involves_dims(size
, isl_dim_in
, 0, dim
))
2750 isl_pw_aff_free(size
);
2752 size
= isl_pw_aff_drop_dims(size
,
2753 isl_dim_in
, 0, dim
);
2754 array
= update_size(array
, i
, size
);
2759 pet_expr_free(expr
);
2764 /* Does "decl" have a definition that we can keep track of in a pet_type?
2766 static bool has_printable_definition(RecordDecl
*decl
)
2768 if (!decl
->getDeclName())
2770 return decl
->getLexicalDeclContext() == decl
->getDeclContext();
2773 /* Add all TypedefType objects that appear when dereferencing "type"
2776 static void insert_intermediate_typedefs(PetTypes
*types
, QualType type
)
2778 type
= pet_clang_base_or_typedef_type(type
);
2779 while (isa
<TypedefType
>(type
)) {
2780 const TypedefType
*tt
;
2782 tt
= cast
<TypedefType
>(type
);
2783 types
->insert(tt
->getDecl());
2784 type
= tt
->desugar();
2785 type
= pet_clang_base_or_typedef_type(type
);
2789 /* Construct and return a pet_array corresponding to the variable
2790 * represented by "id".
2791 * In particular, initialize array->extent to
2793 * { name[i_1,...,i_d] : i_1,...,i_d >= 0 }
2795 * and then call set_upper_bounds to set the upper bounds on the indices
2796 * based on the type of the variable. The upper bounds are converted
2797 * to affine expressions within the context "pc".
2799 * If the base type is that of a record with a top-level definition or
2800 * of a typedef and if "types" is not null, then the RecordDecl or
2801 * TypedefType corresponding to the type, as well as any intermediate
2802 * TypedefType, is added to "types".
2804 * If the base type is that of a record with no top-level definition,
2805 * then we replace it by "<subfield>".
2807 * If the variable is a scalar, i.e., a zero-dimensional array,
2808 * then the "const" qualifier, if any, is removed from the base type.
2809 * This makes it easier for users of pet to turn initializations
2812 struct pet_array
*PetScan::extract_array(__isl_keep isl_id
*id
,
2813 PetTypes
*types
, __isl_keep pet_context
*pc
)
2815 struct pet_array
*array
;
2816 QualType qt
= pet_id_get_array_type(id
);
2817 int depth
= pet_clang_array_depth(qt
);
2818 QualType base
= pet_clang_base_type(qt
);
2822 array
= isl_calloc_type(ctx
, struct pet_array
);
2826 space
= isl_space_set_alloc(ctx
, 0, depth
);
2827 space
= isl_space_set_tuple_id(space
, isl_dim_set
, isl_id_copy(id
));
2829 array
->extent
= isl_set_nat_universe(space
);
2831 space
= isl_space_params_alloc(ctx
, 0);
2832 array
->context
= isl_set_universe(space
);
2834 array
= set_upper_bounds(array
, pc
);
2839 base
.removeLocalConst();
2840 name
= base
.getAsString();
2843 insert_intermediate_typedefs(types
, qt
);
2844 if (isa
<TypedefType
>(base
)) {
2845 types
->insert(cast
<TypedefType
>(base
)->getDecl());
2846 } else if (base
->isRecordType()) {
2847 RecordDecl
*decl
= pet_clang_record_decl(base
);
2848 TypedefNameDecl
*typedecl
;
2849 typedecl
= decl
->getTypedefNameForAnonDecl();
2851 types
->insert(typedecl
);
2852 else if (has_printable_definition(decl
))
2853 types
->insert(decl
);
2855 name
= "<subfield>";
2859 array
->element_type
= strdup(name
.c_str());
2860 array
->element_is_record
= base
->isRecordType();
2861 array
->element_size
= size_in_bytes(ast_context
, base
);
2866 /* Construct and return a pet_array corresponding to the variable "decl".
2868 struct pet_array
*PetScan::extract_array(ValueDecl
*decl
,
2869 PetTypes
*types
, __isl_keep pet_context
*pc
)
2874 id
= pet_id_from_decl(ctx
, decl
);
2875 array
= extract_array(id
, types
, pc
);
2881 /* Construct and return a pet_array corresponding to the sequence
2882 * of declarations represented by "decls".
2883 * The upper bounds of the array are converted to affine expressions
2884 * within the context "pc".
2885 * If the sequence contains a single declaration, then it corresponds
2886 * to a simple array access. Otherwise, it corresponds to a member access,
2887 * with the declaration for the substructure following that of the containing
2888 * structure in the sequence of declarations.
2889 * We start with the outermost substructure and then combine it with
2890 * information from the inner structures.
2892 * Additionally, keep track of all required types in "types".
2894 struct pet_array
*PetScan::extract_array(__isl_keep isl_id_list
*decls
,
2895 PetTypes
*types
, __isl_keep pet_context
*pc
)
2899 struct pet_array
*array
;
2901 id
= isl_id_list_get_id(decls
, 0);
2902 array
= extract_array(id
, types
, pc
);
2905 n
= isl_id_list_n_id(decls
);
2906 for (i
= 1; i
< n
; ++i
) {
2907 struct pet_array
*parent
;
2908 const char *base_name
, *field_name
;
2912 id
= isl_id_list_get_id(decls
, i
);
2913 array
= extract_array(id
, types
, pc
);
2916 return pet_array_free(parent
);
2918 base_name
= isl_set_get_tuple_name(parent
->extent
);
2919 field_name
= isl_set_get_tuple_name(array
->extent
);
2920 product_name
= pet_array_member_access_name(ctx
,
2921 base_name
, field_name
);
2923 array
->extent
= isl_set_product(isl_set_copy(parent
->extent
),
2926 array
->extent
= isl_set_set_tuple_name(array
->extent
,
2928 array
->context
= isl_set_intersect(array
->context
,
2929 isl_set_copy(parent
->context
));
2931 pet_array_free(parent
);
2934 if (!array
->extent
|| !array
->context
|| !product_name
)
2935 return pet_array_free(array
);
2941 static struct pet_scop
*add_type(isl_ctx
*ctx
, struct pet_scop
*scop
,
2942 RecordDecl
*decl
, Preprocessor
&PP
, PetTypes
&types
,
2943 std::set
<TypeDecl
*> &types_done
);
2944 static struct pet_scop
*add_type(isl_ctx
*ctx
, struct pet_scop
*scop
,
2945 TypedefNameDecl
*decl
, Preprocessor
&PP
, PetTypes
&types
,
2946 std::set
<TypeDecl
*> &types_done
);
2948 /* For each of the fields of "decl" that is itself a record type
2949 * or a typedef, or an array of such type, add a corresponding pet_type
2952 static struct pet_scop
*add_field_types(isl_ctx
*ctx
, struct pet_scop
*scop
,
2953 RecordDecl
*decl
, Preprocessor
&PP
, PetTypes
&types
,
2954 std::set
<TypeDecl
*> &types_done
)
2956 RecordDecl::field_iterator it
;
2958 for (it
= decl
->field_begin(); it
!= decl
->field_end(); ++it
) {
2959 QualType type
= it
->getType();
2961 type
= pet_clang_base_or_typedef_type(type
);
2962 if (isa
<TypedefType
>(type
)) {
2963 TypedefNameDecl
*typedefdecl
;
2965 typedefdecl
= cast
<TypedefType
>(type
)->getDecl();
2966 scop
= add_type(ctx
, scop
, typedefdecl
,
2967 PP
, types
, types_done
);
2968 } else if (type
->isRecordType()) {
2971 record
= pet_clang_record_decl(type
);
2972 scop
= add_type(ctx
, scop
, record
,
2973 PP
, types
, types_done
);
2980 /* Add a pet_type corresponding to "decl" to "scop", provided
2981 * it is a member of types.records and it has not been added before
2982 * (i.e., it is not a member of "types_done").
2984 * Since we want the user to be able to print the types
2985 * in the order in which they appear in the scop, we need to
2986 * make sure that types of fields in a structure appear before
2987 * that structure. We therefore call ourselves recursively
2988 * through add_field_types on the types of all record subfields.
2990 static struct pet_scop
*add_type(isl_ctx
*ctx
, struct pet_scop
*scop
,
2991 RecordDecl
*decl
, Preprocessor
&PP
, PetTypes
&types
,
2992 std::set
<TypeDecl
*> &types_done
)
2995 llvm::raw_string_ostream
S(s
);
2997 if (types
.records
.find(decl
) == types
.records
.end())
2999 if (types_done
.find(decl
) != types_done
.end())
3002 add_field_types(ctx
, scop
, decl
, PP
, types
, types_done
);
3004 if (strlen(decl
->getName().str().c_str()) == 0)
3007 decl
->print(S
, PrintingPolicy(PP
.getLangOpts()));
3010 scop
->types
[scop
->n_type
] = pet_type_alloc(ctx
,
3011 decl
->getName().str().c_str(), s
.c_str());
3012 if (!scop
->types
[scop
->n_type
])
3013 return pet_scop_free(scop
);
3015 types_done
.insert(decl
);
3022 /* Add a pet_type corresponding to "decl" to "scop", provided
3023 * it is a member of types.typedefs and it has not been added before
3024 * (i.e., it is not a member of "types_done").
3026 * If the underlying type is a structure, then we print the typedef
3027 * ourselves since clang does not print the definition of the structure
3028 * in the typedef. We also make sure in this case that the types of
3029 * the fields in the structure are added first.
3030 * Since the definition of the structure also gets printed this way,
3031 * add it to types_done such that it will not be printed again,
3032 * not even without the typedef.
3034 static struct pet_scop
*add_type(isl_ctx
*ctx
, struct pet_scop
*scop
,
3035 TypedefNameDecl
*decl
, Preprocessor
&PP
, PetTypes
&types
,
3036 std::set
<TypeDecl
*> &types_done
)
3039 llvm::raw_string_ostream
S(s
);
3040 QualType qt
= decl
->getUnderlyingType();
3042 if (types
.typedefs
.find(decl
) == types
.typedefs
.end())
3044 if (types_done
.find(decl
) != types_done
.end())
3047 if (qt
->isRecordType()) {
3048 RecordDecl
*rec
= pet_clang_record_decl(qt
);
3050 add_field_types(ctx
, scop
, rec
, PP
, types
, types_done
);
3052 rec
->print(S
, PrintingPolicy(PP
.getLangOpts()));
3054 S
<< decl
->getName();
3055 types_done
.insert(rec
);
3057 decl
->print(S
, PrintingPolicy(PP
.getLangOpts()));
3061 scop
->types
[scop
->n_type
] = pet_type_alloc(ctx
,
3062 decl
->getName().str().c_str(), s
.c_str());
3063 if (!scop
->types
[scop
->n_type
])
3064 return pet_scop_free(scop
);
3066 types_done
.insert(decl
);
3073 /* Construct a list of pet_arrays, one for each array (or scalar)
3074 * accessed inside "scop", add this list to "scop" and return the result.
3075 * The upper bounds of the arrays are converted to affine expressions
3076 * within the context "pc".
3078 * The context of "scop" is updated with the intersection of
3079 * the contexts of all arrays, i.e., constraints on the parameters
3080 * that ensure that the arrays have a valid (non-negative) size.
3082 * If any of the extracted arrays refers to a member access or
3083 * has a typedef'd type as base type,
3084 * then also add the required types to "scop".
3085 * The typedef types are printed first because their definitions
3086 * may include the definition of a struct and these struct definitions
3087 * should not be printed separately. While the typedef definition
3088 * is being printed, the struct is marked as having been printed as well,
3089 * such that the later printing of the struct by itself can be prevented.
3091 * If the sequence of nested array declarations from which the pet_array
3092 * is extracted appears as the prefix of some other sequence,
3093 * then the pet_array is marked as "outer".
3094 * The arrays that already appear in scop->arrays at the start of
3095 * this function are assumed to be simple arrays, so they are not marked
3098 struct pet_scop
*PetScan::scan_arrays(struct pet_scop
*scop
,
3099 __isl_keep pet_context
*pc
)
3102 array_desc_set arrays
, has_sub
;
3103 array_desc_set::iterator it
;
3105 std::set
<TypeDecl
*> types_done
;
3106 std::set
<clang::RecordDecl
*, less_name
>::iterator records_it
;
3107 std::set
<clang::TypedefNameDecl
*, less_name
>::iterator typedefs_it
;
3109 struct pet_array
**scop_arrays
;
3114 pet_scop_collect_arrays(scop
, arrays
);
3115 if (arrays
.size() == 0)
3118 n_array
= scop
->n_array
;
3120 scop_arrays
= isl_realloc_array(ctx
, scop
->arrays
, struct pet_array
*,
3121 n_array
+ arrays
.size());
3124 scop
->arrays
= scop_arrays
;
3126 for (it
= arrays
.begin(); it
!= arrays
.end(); ++it
) {
3127 isl_id_list
*list
= isl_id_list_copy(*it
);
3128 int n
= isl_id_list_n_id(list
);
3129 list
= isl_id_list_drop(list
, n
- 1, 1);
3130 has_sub
.insert(list
);
3133 for (it
= arrays
.begin(), i
= 0; it
!= arrays
.end(); ++it
, ++i
) {
3134 struct pet_array
*array
;
3135 array
= extract_array(*it
, &types
, pc
);
3136 scop
->arrays
[n_array
+ i
] = array
;
3137 if (!scop
->arrays
[n_array
+ i
])
3139 if (has_sub
.find(*it
) != has_sub
.end())
3142 scop
->context
= isl_set_intersect(scop
->context
,
3143 isl_set_copy(array
->context
));
3148 n
= types
.records
.size() + types
.typedefs
.size();
3152 scop
->types
= isl_alloc_array(ctx
, struct pet_type
*, n
);
3156 for (typedefs_it
= types
.typedefs
.begin();
3157 typedefs_it
!= types
.typedefs
.end(); ++typedefs_it
)
3158 scop
= add_type(ctx
, scop
, *typedefs_it
, PP
, types
, types_done
);
3160 for (records_it
= types
.records
.begin();
3161 records_it
!= types
.records
.end(); ++records_it
)
3162 scop
= add_type(ctx
, scop
, *records_it
, PP
, types
, types_done
);
3166 pet_scop_free(scop
);
3170 /* Bound all parameters in scop->context to the possible values
3171 * of the corresponding C variable.
3173 static struct pet_scop
*add_parameter_bounds(struct pet_scop
*scop
)
3180 n
= isl_set_dim(scop
->context
, isl_dim_param
);
3181 for (int i
= 0; i
< n
; ++i
) {
3185 id
= isl_set_get_dim_id(scop
->context
, isl_dim_param
, i
);
3186 if (pet_nested_in_id(id
)) {
3188 isl_die(isl_set_get_ctx(scop
->context
),
3190 "unresolved nested parameter", goto error
);
3192 decl
= pet_id_get_decl(id
);
3195 scop
->context
= set_parameter_bounds(scop
->context
, i
, decl
);
3203 pet_scop_free(scop
);
3207 /* Construct a pet_scop from the given function.
3209 * If the scop was delimited by scop and endscop pragmas, then we override
3210 * the file offsets by those derived from the pragmas.
3212 struct pet_scop
*PetScan::scan(FunctionDecl
*fd
)
3217 stmt
= fd
->getBody();
3219 if (options
->autodetect
) {
3220 set_current_stmt(stmt
);
3221 scop
= extract_scop(extract(stmt
, true));
3223 current_line
= loc
.start_line
;
3225 scop
= pet_scop_update_start_end(scop
, loc
.start
, loc
.end
);
3227 scop
= add_parameter_bounds(scop
);
3228 scop
= pet_scop_gist(scop
, value_bounds
);
3233 /* Update this->last_line and this->current_line based on the fact
3234 * that we are about to consider "stmt".
3236 void PetScan::set_current_stmt(Stmt
*stmt
)
3238 SourceLocation loc
= stmt
->getLocStart();
3239 SourceManager
&SM
= PP
.getSourceManager();
3241 last_line
= current_line
;
3242 current_line
= SM
.getExpansionLineNumber(loc
);
3245 /* Is the current statement marked by an independent pragma?
3246 * That is, is there an independent pragma on a line between
3247 * the line of the current statement and the line of the previous statement.
3248 * The search is not implemented very efficiently. We currently
3249 * assume that there are only a few independent pragmas, if any.
3251 bool PetScan::is_current_stmt_marked_independent()
3253 for (unsigned i
= 0; i
< independent
.size(); ++i
) {
3254 unsigned line
= independent
[i
].line
;
3256 if (last_line
< line
&& line
< current_line
)