4 #include <clang/AST/ASTDiagnostic.h>
5 #include <clang/AST/Expr.h>
6 #include <clang/AST/RecursiveASTVisitor.h>
15 #include "scop_plus.h"
20 using namespace clang
;
22 /* Look for any assignments to scalar variables in part of the parse
23 * tree and set assigned_value to NULL for each of them.
24 * Also reset assigned_value if the address of a scalar variable
27 * This ensures that we won't use any previously stored value
28 * in the current subtree and its parents.
30 struct clear_assignments
: RecursiveASTVisitor
<clear_assignments
> {
31 map
<ValueDecl
*, Expr
*> &assigned_value
;
33 clear_assignments(map
<ValueDecl
*, Expr
*> &assigned_value
) :
34 assigned_value(assigned_value
) {}
36 bool VisitUnaryOperator(UnaryOperator
*expr
) {
41 if (expr
->getOpcode() != UO_AddrOf
)
44 arg
= expr
->getSubExpr();
45 if (arg
->getStmtClass() != Stmt::DeclRefExprClass
)
47 ref
= cast
<DeclRefExpr
>(arg
);
48 decl
= ref
->getDecl();
49 assigned_value
[decl
] = NULL
;
53 bool VisitBinaryOperator(BinaryOperator
*expr
) {
58 if (!expr
->isAssignmentOp())
61 if (lhs
->getStmtClass() != Stmt::DeclRefExprClass
)
63 ref
= cast
<DeclRefExpr
>(lhs
);
64 decl
= ref
->getDecl();
65 assigned_value
[decl
] = NULL
;
70 /* Keep a copy of the currently assigned values.
72 * Any variable that is assigned a value inside the current scope
73 * is removed again when we leave the scope (either because it wasn't
74 * stored in the cache or because it has a different value in the cache).
76 struct assigned_value_cache
{
77 map
<ValueDecl
*, Expr
*> &assigned_value
;
78 map
<ValueDecl
*, Expr
*> cache
;
80 assigned_value_cache(map
<ValueDecl
*, Expr
*> &assigned_value
) :
81 assigned_value(assigned_value
), cache(assigned_value
) {}
82 ~assigned_value_cache() {
83 map
<ValueDecl
*, Expr
*>::iterator it
= cache
.begin();
84 for (it
= assigned_value
.begin(); it
!= assigned_value
.end();
87 (cache
.find(it
->first
) != cache
.end() &&
88 cache
[it
->first
] != it
->second
))
89 cache
[it
->first
] = NULL
;
91 assigned_value
= cache
;
95 /* Called if we found something we (currently) cannot handle.
96 * We'll provide more informative warnings later.
98 * We only actually complain if autodetect is false.
100 void PetScan::unsupported(Stmt
*stmt
)
105 SourceLocation loc
= stmt
->getLocStart();
106 Diagnostic
&diag
= PP
.getDiagnostics();
107 unsigned id
= diag
.getCustomDiagID(Diagnostic::Warning
, "unsupported");
108 DiagnosticBuilder B
= diag
.Report(loc
, id
) << stmt
->getSourceRange();
111 /* Extract an integer from "expr" and store it in "v".
113 int PetScan::extract_int(IntegerLiteral
*expr
, isl_int
*v
)
115 const Type
*type
= expr
->getType().getTypePtr();
116 int is_signed
= type
->hasSignedIntegerRepresentation();
119 int64_t i
= expr
->getValue().getSExtValue();
120 isl_int_set_si(*v
, i
);
122 uint64_t i
= expr
->getValue().getZExtValue();
123 isl_int_set_ui(*v
, i
);
129 /* Extract an affine expression from the IntegerLiteral "expr".
131 __isl_give isl_pw_aff
*PetScan::extract_affine(IntegerLiteral
*expr
)
133 isl_space
*dim
= isl_space_set_alloc(ctx
, 0, 0);
134 isl_local_space
*ls
= isl_local_space_from_space(isl_space_copy(dim
));
135 isl_aff
*aff
= isl_aff_zero_on_domain(ls
);
136 isl_set
*dom
= isl_set_universe(dim
);
140 extract_int(expr
, &v
);
141 aff
= isl_aff_add_constant(aff
, v
);
144 return isl_pw_aff_alloc(dom
, aff
);
147 /* Extract an affine expression from the APInt "val".
149 __isl_give isl_pw_aff
*PetScan::extract_affine(const llvm::APInt
&val
)
151 isl_space
*dim
= isl_space_set_alloc(ctx
, 0, 0);
152 isl_local_space
*ls
= isl_local_space_from_space(isl_space_copy(dim
));
153 isl_aff
*aff
= isl_aff_zero_on_domain(ls
);
154 isl_set
*dom
= isl_set_universe(dim
);
158 isl_int_set_ui(v
, val
.getZExtValue());
159 aff
= isl_aff_add_constant(aff
, v
);
162 return isl_pw_aff_alloc(dom
, aff
);
165 __isl_give isl_pw_aff
*PetScan::extract_affine(ImplicitCastExpr
*expr
)
167 return extract_affine(expr
->getSubExpr());
170 /* Extract an affine expression from the DeclRefExpr "expr".
172 * If we have recorded an expression that was assigned to the variable
173 * before, then we convert this expressoin to an isl_pw_aff if it is
174 * affine and to an extra parameter otherwise (provided nesting_enabled is set).
176 * Otherwise, we simply return an expression that is equal
177 * to a parameter corresponding to the referenced variable.
179 __isl_give isl_pw_aff
*PetScan::extract_affine(DeclRefExpr
*expr
)
181 ValueDecl
*decl
= expr
->getDecl();
182 const Type
*type
= decl
->getType().getTypePtr();
188 if (!type
->isIntegerType()) {
193 if (assigned_value
.find(decl
) != assigned_value
.end() &&
194 assigned_value
[decl
] != NULL
) {
195 if (is_affine(assigned_value
[decl
]))
196 return extract_affine(assigned_value
[decl
]);
198 return non_affine(expr
);
201 id
= isl_id_alloc(ctx
, decl
->getName().str().c_str(), decl
);
202 dim
= isl_space_set_alloc(ctx
, 1, 0);
204 dim
= isl_space_set_dim_id(dim
, isl_dim_param
, 0, id
);
206 dom
= isl_set_universe(isl_space_copy(dim
));
207 aff
= isl_aff_zero_on_domain(isl_local_space_from_space(dim
));
208 aff
= isl_aff_add_coefficient_si(aff
, isl_dim_param
, 0, 1);
210 return isl_pw_aff_alloc(dom
, aff
);
213 /* Extract an affine expression from an integer division operation.
214 * In particular, if "expr" is lhs/rhs, then return
216 * lhs >= 0 ? floor(lhs/rhs) : ceil(lhs/rhs)
218 * The second argument (rhs) is required to be a (positive) integer constant.
220 __isl_give isl_pw_aff
*PetScan::extract_affine_div(BinaryOperator
*expr
)
223 isl_pw_aff
*lhs
, *lhs_f
, *lhs_c
;
228 rhs_expr
= expr
->getRHS();
229 if (rhs_expr
->getStmtClass() != Stmt::IntegerLiteralClass
) {
234 lhs
= extract_affine(expr
->getLHS());
235 cond
= isl_pw_aff_nonneg_set(isl_pw_aff_copy(lhs
));
238 extract_int(cast
<IntegerLiteral
>(rhs_expr
), &v
);
239 lhs
= isl_pw_aff_scale_down(lhs
, v
);
242 lhs_f
= isl_pw_aff_floor(isl_pw_aff_copy(lhs
));
243 lhs_c
= isl_pw_aff_ceil(lhs
);
244 res
= isl_pw_aff_cond(cond
, lhs_f
, lhs_c
);
249 /* Extract an affine expression from a modulo operation.
250 * In particular, if "expr" is lhs/rhs, then return
252 * lhs - rhs * (lhs >= 0 ? floor(lhs/rhs) : ceil(lhs/rhs))
254 * The second argument (rhs) is required to be a (positive) integer constant.
256 __isl_give isl_pw_aff
*PetScan::extract_affine_mod(BinaryOperator
*expr
)
259 isl_pw_aff
*lhs
, *lhs_f
, *lhs_c
;
264 rhs_expr
= expr
->getRHS();
265 if (rhs_expr
->getStmtClass() != Stmt::IntegerLiteralClass
) {
270 lhs
= extract_affine(expr
->getLHS());
271 cond
= isl_pw_aff_nonneg_set(isl_pw_aff_copy(lhs
));
274 extract_int(cast
<IntegerLiteral
>(rhs_expr
), &v
);
275 res
= isl_pw_aff_scale_down(isl_pw_aff_copy(lhs
), v
);
277 lhs_f
= isl_pw_aff_floor(isl_pw_aff_copy(res
));
278 lhs_c
= isl_pw_aff_ceil(res
);
279 res
= isl_pw_aff_cond(cond
, lhs_f
, lhs_c
);
281 res
= isl_pw_aff_scale(res
, v
);
284 res
= isl_pw_aff_sub(lhs
, res
);
289 /* Extract an affine expression from a multiplication operation.
290 * This is only allowed if at least one of the two arguments
291 * is a (piecewise) constant.
293 __isl_give isl_pw_aff
*PetScan::extract_affine_mul(BinaryOperator
*expr
)
298 lhs
= extract_affine(expr
->getLHS());
299 rhs
= extract_affine(expr
->getRHS());
301 if (!isl_pw_aff_is_cst(lhs
) && !isl_pw_aff_is_cst(rhs
)) {
302 isl_pw_aff_free(lhs
);
303 isl_pw_aff_free(rhs
);
308 return isl_pw_aff_mul(lhs
, rhs
);
311 /* Extract an affine expression from an addition or subtraction operation.
313 __isl_give isl_pw_aff
*PetScan::extract_affine_add(BinaryOperator
*expr
)
318 lhs
= extract_affine(expr
->getLHS());
319 rhs
= extract_affine(expr
->getRHS());
321 switch (expr
->getOpcode()) {
323 return isl_pw_aff_add(lhs
, rhs
);
325 return isl_pw_aff_sub(lhs
, rhs
);
327 isl_pw_aff_free(lhs
);
328 isl_pw_aff_free(rhs
);
338 static __isl_give isl_pw_aff
*wrap(__isl_take isl_pw_aff
*pwaff
,
344 isl_int_set_si(mod
, 1);
345 isl_int_mul_2exp(mod
, mod
, width
);
347 pwaff
= isl_pw_aff_mod(pwaff
, mod
);
354 /* Extract an affine expression from some binary operations.
355 * If the result of the expression is unsigned, then we wrap it
356 * based on the size of the type.
358 __isl_give isl_pw_aff
*PetScan::extract_affine(BinaryOperator
*expr
)
362 switch (expr
->getOpcode()) {
365 res
= extract_affine_add(expr
);
368 res
= extract_affine_div(expr
);
371 res
= extract_affine_mod(expr
);
374 res
= extract_affine_mul(expr
);
381 if (expr
->getType()->isUnsignedIntegerType())
382 res
= wrap(res
, ast_context
.getIntWidth(expr
->getType()));
387 /* Extract an affine expression from a negation operation.
389 __isl_give isl_pw_aff
*PetScan::extract_affine(UnaryOperator
*expr
)
391 if (expr
->getOpcode() == UO_Minus
)
392 return isl_pw_aff_neg(extract_affine(expr
->getSubExpr()));
398 __isl_give isl_pw_aff
*PetScan::extract_affine(ParenExpr
*expr
)
400 return extract_affine(expr
->getSubExpr());
403 /* Extract an affine expression from some special function calls.
404 * In particular, we handle "min", "max", "ceild" and "floord".
405 * In case of the latter two, the second argument needs to be
406 * a (positive) integer constant.
408 __isl_give isl_pw_aff
*PetScan::extract_affine(CallExpr
*expr
)
412 isl_pw_aff
*aff1
, *aff2
;
414 fd
= expr
->getDirectCallee();
420 name
= fd
->getDeclName().getAsString();
421 if (!(expr
->getNumArgs() == 2 && name
== "min") &&
422 !(expr
->getNumArgs() == 2 && name
== "max") &&
423 !(expr
->getNumArgs() == 2 && name
== "floord") &&
424 !(expr
->getNumArgs() == 2 && name
== "ceild")) {
429 if (name
== "min" || name
== "max") {
430 aff1
= extract_affine(expr
->getArg(0));
431 aff2
= extract_affine(expr
->getArg(1));
434 aff1
= isl_pw_aff_min(aff1
, aff2
);
436 aff1
= isl_pw_aff_max(aff1
, aff2
);
437 } else if (name
== "floord" || name
== "ceild") {
439 Expr
*arg2
= expr
->getArg(1);
441 if (arg2
->getStmtClass() != Stmt::IntegerLiteralClass
) {
445 aff1
= extract_affine(expr
->getArg(0));
447 extract_int(cast
<IntegerLiteral
>(arg2
), &v
);
448 aff1
= isl_pw_aff_scale_down(aff1
, v
);
450 if (name
== "floord")
451 aff1
= isl_pw_aff_floor(aff1
);
453 aff1
= isl_pw_aff_ceil(aff1
);
463 /* This method is called when we come across a non-affine expression.
464 * If nesting is allowed, we return a new parameter that corresponds
465 * to the non-affine expression. Otherwise, we simply complain.
467 * The new parameter is resolved in resolve_nested.
469 isl_pw_aff
*PetScan::non_affine(Expr
*expr
)
476 if (!nesting_enabled
) {
481 id
= isl_id_alloc(ctx
, NULL
, expr
);
482 dim
= isl_space_set_alloc(ctx
, 1, 0);
484 dim
= isl_space_set_dim_id(dim
, isl_dim_param
, 0, id
);
486 dom
= isl_set_universe(isl_space_copy(dim
));
487 aff
= isl_aff_zero_on_domain(isl_local_space_from_space(dim
));
488 aff
= isl_aff_add_coefficient_si(aff
, isl_dim_param
, 0, 1);
490 return isl_pw_aff_alloc(dom
, aff
);
493 /* Affine expressions are not supposed to contain array accesses,
494 * but if nesting is allowed, we return a parameter corresponding
495 * to the array access.
497 __isl_give isl_pw_aff
*PetScan::extract_affine(ArraySubscriptExpr
*expr
)
499 return non_affine(expr
);
502 /* Extract an affine expression from a conditional operation.
504 __isl_give isl_pw_aff
*PetScan::extract_affine(ConditionalOperator
*expr
)
507 isl_pw_aff
*lhs
, *rhs
;
509 cond
= extract_condition(expr
->getCond());
510 lhs
= extract_affine(expr
->getTrueExpr());
511 rhs
= extract_affine(expr
->getFalseExpr());
513 return isl_pw_aff_cond(cond
, lhs
, rhs
);
516 /* Extract an affine expression, if possible, from "expr".
517 * Otherwise return NULL.
519 __isl_give isl_pw_aff
*PetScan::extract_affine(Expr
*expr
)
521 switch (expr
->getStmtClass()) {
522 case Stmt::ImplicitCastExprClass
:
523 return extract_affine(cast
<ImplicitCastExpr
>(expr
));
524 case Stmt::IntegerLiteralClass
:
525 return extract_affine(cast
<IntegerLiteral
>(expr
));
526 case Stmt::DeclRefExprClass
:
527 return extract_affine(cast
<DeclRefExpr
>(expr
));
528 case Stmt::BinaryOperatorClass
:
529 return extract_affine(cast
<BinaryOperator
>(expr
));
530 case Stmt::UnaryOperatorClass
:
531 return extract_affine(cast
<UnaryOperator
>(expr
));
532 case Stmt::ParenExprClass
:
533 return extract_affine(cast
<ParenExpr
>(expr
));
534 case Stmt::CallExprClass
:
535 return extract_affine(cast
<CallExpr
>(expr
));
536 case Stmt::ArraySubscriptExprClass
:
537 return extract_affine(cast
<ArraySubscriptExpr
>(expr
));
538 case Stmt::ConditionalOperatorClass
:
539 return extract_affine(cast
<ConditionalOperator
>(expr
));
546 __isl_give isl_map
*PetScan::extract_access(ImplicitCastExpr
*expr
)
548 return extract_access(expr
->getSubExpr());
551 /* Return the depth of an array of the given type.
553 static int array_depth(const Type
*type
)
555 if (type
->isPointerType())
556 return 1 + array_depth(type
->getPointeeType().getTypePtr());
557 if (type
->isArrayType()) {
558 const ArrayType
*atype
;
559 type
= type
->getCanonicalTypeInternal().getTypePtr();
560 atype
= cast
<ArrayType
>(type
);
561 return 1 + array_depth(atype
->getElementType().getTypePtr());
566 /* Return the element type of the given array type.
568 static QualType
base_type(QualType qt
)
570 const Type
*type
= qt
.getTypePtr();
572 if (type
->isPointerType())
573 return base_type(type
->getPointeeType());
574 if (type
->isArrayType()) {
575 const ArrayType
*atype
;
576 type
= type
->getCanonicalTypeInternal().getTypePtr();
577 atype
= cast
<ArrayType
>(type
);
578 return base_type(atype
->getElementType());
583 /* Check if the element type corresponding to the given array type
584 * has a const qualifier.
586 static bool const_base(QualType qt
)
588 const Type
*type
= qt
.getTypePtr();
590 if (type
->isPointerType())
591 return const_base(type
->getPointeeType());
592 if (type
->isArrayType()) {
593 const ArrayType
*atype
;
594 type
= type
->getCanonicalTypeInternal().getTypePtr();
595 atype
= cast
<ArrayType
>(type
);
596 return const_base(atype
->getElementType());
599 return qt
.isConstQualified();
602 /* Extract an access relation from a reference to a variable.
603 * If the variable has name "A" and its type corresponds to an
604 * array of depth d, then the returned access relation is of the
607 * { [] -> A[i_1,...,i_d] }
609 __isl_give isl_map
*PetScan::extract_access(DeclRefExpr
*expr
)
611 ValueDecl
*decl
= expr
->getDecl();
612 int depth
= array_depth(decl
->getType().getTypePtr());
613 isl_id
*id
= isl_id_alloc(ctx
, decl
->getName().str().c_str(), decl
);
614 isl_space
*dim
= isl_space_alloc(ctx
, 0, 0, depth
);
617 dim
= isl_space_set_tuple_id(dim
, isl_dim_out
, id
);
619 access_rel
= isl_map_universe(dim
);
624 /* Extract an access relation from an integer contant.
625 * If the value of the constant is "v", then the returned access relation
630 __isl_give isl_map
*PetScan::extract_access(IntegerLiteral
*expr
)
632 return isl_map_from_pw_aff(extract_affine(expr
));
635 /* Try and extract an access relation from the given Expr.
636 * Return NULL if it doesn't work out.
638 __isl_give isl_map
*PetScan::extract_access(Expr
*expr
)
640 switch (expr
->getStmtClass()) {
641 case Stmt::ImplicitCastExprClass
:
642 return extract_access(cast
<ImplicitCastExpr
>(expr
));
643 case Stmt::DeclRefExprClass
:
644 return extract_access(cast
<DeclRefExpr
>(expr
));
645 case Stmt::ArraySubscriptExprClass
:
646 return extract_access(cast
<ArraySubscriptExpr
>(expr
));
653 /* Assign the affine expression "index" to the output dimension "pos" of "map"
654 * and return the result.
656 __isl_give isl_map
*set_index(__isl_take isl_map
*map
, int pos
,
657 __isl_take isl_pw_aff
*index
)
660 int len
= isl_map_dim(map
, isl_dim_out
);
663 index_map
= isl_map_from_pw_aff(index
);
664 index_map
= isl_map_insert_dims(index_map
, isl_dim_out
, 0, pos
);
665 index_map
= isl_map_add_dims(index_map
, isl_dim_out
, len
- pos
- 1);
666 id
= isl_map_get_tuple_id(map
, isl_dim_out
);
667 index_map
= isl_map_set_tuple_id(index_map
, isl_dim_out
, id
);
669 map
= isl_map_intersect(map
, index_map
);
674 /* Extract an access relation from the given array subscript expression.
675 * If nesting is allowed in general, then we turn it on while
676 * examining the index expression.
678 * We first extract an access relation from the base.
679 * This will result in an access relation with a range that corresponds
680 * to the array being accessed and with earlier indices filled in already.
681 * We then extract the current index and fill that in as well.
682 * The position of the current index is based on the type of base.
683 * If base is the actual array variable, then the depth of this type
684 * will be the same as the depth of the array and we will fill in
685 * the first array index.
686 * Otherwise, the depth of the base type will be smaller and we will fill
689 __isl_give isl_map
*PetScan::extract_access(ArraySubscriptExpr
*expr
)
691 Expr
*base
= expr
->getBase();
692 Expr
*idx
= expr
->getIdx();
694 isl_map
*base_access
;
696 int depth
= array_depth(base
->getType().getTypePtr());
698 bool save_nesting
= nesting_enabled
;
700 nesting_enabled
= allow_nested
;
702 base_access
= extract_access(base
);
703 index
= extract_affine(idx
);
705 nesting_enabled
= save_nesting
;
707 pos
= isl_map_dim(base_access
, isl_dim_out
) - depth
;
708 access
= set_index(base_access
, pos
, index
);
713 /* Check if "expr" calls function "minmax" with two arguments and if so
714 * make lhs and rhs refer to these two arguments.
716 static bool is_minmax(Expr
*expr
, const char *minmax
, Expr
*&lhs
, Expr
*&rhs
)
722 if (expr
->getStmtClass() != Stmt::CallExprClass
)
725 call
= cast
<CallExpr
>(expr
);
726 fd
= call
->getDirectCallee();
730 if (call
->getNumArgs() != 2)
733 name
= fd
->getDeclName().getAsString();
737 lhs
= call
->getArg(0);
738 rhs
= call
->getArg(1);
743 /* Check if "expr" is of the form min(lhs, rhs) and if so make
744 * lhs and rhs refer to the two arguments.
746 static bool is_min(Expr
*expr
, Expr
*&lhs
, Expr
*&rhs
)
748 return is_minmax(expr
, "min", lhs
, rhs
);
751 /* Check if "expr" is of the form max(lhs, rhs) and if so make
752 * lhs and rhs refer to the two arguments.
754 static bool is_max(Expr
*expr
, Expr
*&lhs
, Expr
*&rhs
)
756 return is_minmax(expr
, "max", lhs
, rhs
);
759 /* Extract a set of values satisfying the comparison "LHS op RHS"
760 * "comp" is the original statement that "LHS op RHS" is derived from
761 * and is used for diagnostics.
763 * If the comparison is of the form
767 * then the set is constructed as the intersection of the set corresponding
772 * A similar optimization is performed for max(a,b) <= c.
773 * We do this because that will lead to simpler representations of the set.
774 * If isl is ever enhanced to explicitly deal with min and max expressions,
775 * this optimization can be removed.
777 __isl_give isl_set
*PetScan::extract_comparison(BinaryOperatorKind op
,
778 Expr
*LHS
, Expr
*RHS
, Stmt
*comp
)
785 return extract_comparison(BO_LT
, RHS
, LHS
, comp
);
787 return extract_comparison(BO_LE
, RHS
, LHS
, comp
);
789 if (op
== BO_LT
|| op
== BO_LE
) {
791 isl_set
*set1
, *set2
;
792 if (is_min(RHS
, expr1
, expr2
)) {
793 set1
= extract_comparison(op
, LHS
, expr1
, comp
);
794 set2
= extract_comparison(op
, LHS
, expr2
, comp
);
795 return isl_set_intersect(set1
, set2
);
797 if (is_max(LHS
, expr1
, expr2
)) {
798 set1
= extract_comparison(op
, expr1
, RHS
, comp
);
799 set2
= extract_comparison(op
, expr2
, RHS
, comp
);
800 return isl_set_intersect(set1
, set2
);
804 lhs
= extract_affine(LHS
);
805 rhs
= extract_affine(RHS
);
809 cond
= isl_pw_aff_lt_set(lhs
, rhs
);
812 cond
= isl_pw_aff_le_set(lhs
, rhs
);
815 cond
= isl_pw_aff_eq_set(lhs
, rhs
);
818 cond
= isl_pw_aff_ne_set(lhs
, rhs
);
821 isl_pw_aff_free(lhs
);
822 isl_pw_aff_free(rhs
);
827 cond
= isl_set_coalesce(cond
);
832 __isl_give isl_set
*PetScan::extract_comparison(BinaryOperator
*comp
)
834 return extract_comparison(comp
->getOpcode(), comp
->getLHS(),
835 comp
->getRHS(), comp
);
838 /* Extract a set of values satisfying the negation (logical not)
839 * of a subexpression.
841 __isl_give isl_set
*PetScan::extract_boolean(UnaryOperator
*op
)
845 cond
= extract_condition(op
->getSubExpr());
847 return isl_set_complement(cond
);
850 /* Extract a set of values satisfying the union (logical or)
851 * or intersection (logical and) of two subexpressions.
853 __isl_give isl_set
*PetScan::extract_boolean(BinaryOperator
*comp
)
859 lhs
= extract_condition(comp
->getLHS());
860 rhs
= extract_condition(comp
->getRHS());
862 switch (comp
->getOpcode()) {
864 cond
= isl_set_intersect(lhs
, rhs
);
867 cond
= isl_set_union(lhs
, rhs
);
879 __isl_give isl_set
*PetScan::extract_condition(UnaryOperator
*expr
)
881 switch (expr
->getOpcode()) {
883 return extract_boolean(expr
);
890 /* Extract a set of values satisfying the condition "expr != 0".
892 __isl_give isl_set
*PetScan::extract_implicit_condition(Expr
*expr
)
894 return isl_pw_aff_non_zero_set(extract_affine(expr
));
897 /* Extract a set of values satisfying the condition expressed by "expr".
899 * If the expression doesn't look like a condition, we assume it
900 * is an affine expression and return the condition "expr != 0".
902 __isl_give isl_set
*PetScan::extract_condition(Expr
*expr
)
904 BinaryOperator
*comp
;
907 return isl_set_universe(isl_space_set_alloc(ctx
, 0, 0));
909 if (expr
->getStmtClass() == Stmt::ParenExprClass
)
910 return extract_condition(cast
<ParenExpr
>(expr
)->getSubExpr());
912 if (expr
->getStmtClass() == Stmt::UnaryOperatorClass
)
913 return extract_condition(cast
<UnaryOperator
>(expr
));
915 if (expr
->getStmtClass() != Stmt::BinaryOperatorClass
)
916 return extract_implicit_condition(expr
);
918 comp
= cast
<BinaryOperator
>(expr
);
919 switch (comp
->getOpcode()) {
926 return extract_comparison(comp
);
929 return extract_boolean(comp
);
931 return extract_implicit_condition(expr
);
935 static enum pet_op_type
UnaryOperatorKind2pet_op_type(UnaryOperatorKind kind
)
945 static enum pet_op_type
BinaryOperatorKind2pet_op_type(BinaryOperatorKind kind
)
949 return pet_op_add_assign
;
951 return pet_op_sub_assign
;
953 return pet_op_mul_assign
;
955 return pet_op_div_assign
;
957 return pet_op_assign
;
979 /* Construct a pet_expr representing a unary operator expression.
981 struct pet_expr
*PetScan::extract_expr(UnaryOperator
*expr
)
983 struct pet_expr
*arg
;
986 op
= UnaryOperatorKind2pet_op_type(expr
->getOpcode());
987 if (op
== pet_op_last
) {
992 arg
= extract_expr(expr
->getSubExpr());
994 return pet_expr_new_unary(ctx
, op
, arg
);
997 /* Mark the given access pet_expr as a write.
998 * If a scalar is being accessed, then mark its value
999 * as unknown in assigned_value.
1001 void PetScan::mark_write(struct pet_expr
*access
)
1006 access
->acc
.write
= 1;
1007 access
->acc
.read
= 0;
1009 if (isl_map_dim(access
->acc
.access
, isl_dim_out
) != 0)
1012 id
= isl_map_get_tuple_id(access
->acc
.access
, isl_dim_out
);
1013 decl
= (ValueDecl
*) isl_id_get_user(id
);
1014 assigned_value
[decl
] = NULL
;
1018 /* Construct a pet_expr representing a binary operator expression.
1020 * If the top level operator is an assignment and the LHS is an access,
1021 * then we mark that access as a write. If the operator is a compound
1022 * assignment, the access is marked as both a read and a write.
1024 * If "expr" assigns something to a scalar variable, then we keep track
1025 * of the assigned expression in assigned_value so that we can plug
1026 * it in when we later come across the same variable.
1028 struct pet_expr
*PetScan::extract_expr(BinaryOperator
*expr
)
1030 struct pet_expr
*lhs
, *rhs
;
1031 enum pet_op_type op
;
1033 op
= BinaryOperatorKind2pet_op_type(expr
->getOpcode());
1034 if (op
== pet_op_last
) {
1039 lhs
= extract_expr(expr
->getLHS());
1040 rhs
= extract_expr(expr
->getRHS());
1042 if (expr
->isAssignmentOp() && lhs
&& lhs
->type
== pet_expr_access
) {
1044 if (expr
->isCompoundAssignmentOp())
1048 if (expr
->getOpcode() == BO_Assign
&&
1049 lhs
&& lhs
->type
== pet_expr_access
&&
1050 isl_map_dim(lhs
->acc
.access
, isl_dim_out
) == 0) {
1051 isl_id
*id
= isl_map_get_tuple_id(lhs
->acc
.access
, isl_dim_out
);
1052 ValueDecl
*decl
= (ValueDecl
*) isl_id_get_user(id
);
1053 assigned_value
[decl
] = expr
->getRHS();
1057 return pet_expr_new_binary(ctx
, op
, lhs
, rhs
);
1060 /* Construct a pet_expr representing a conditional operation.
1062 struct pet_expr
*PetScan::extract_expr(ConditionalOperator
*expr
)
1064 struct pet_expr
*cond
, *lhs
, *rhs
;
1066 cond
= extract_expr(expr
->getCond());
1067 lhs
= extract_expr(expr
->getTrueExpr());
1068 rhs
= extract_expr(expr
->getFalseExpr());
1070 return pet_expr_new_ternary(ctx
, cond
, lhs
, rhs
);
1073 struct pet_expr
*PetScan::extract_expr(ImplicitCastExpr
*expr
)
1075 return extract_expr(expr
->getSubExpr());
1078 /* Construct a pet_expr representing a floating point value.
1080 struct pet_expr
*PetScan::extract_expr(FloatingLiteral
*expr
)
1082 return pet_expr_new_double(ctx
, expr
->getValueAsApproximateDouble());
1085 /* Extract an access relation from "expr" and then convert it into
1088 struct pet_expr
*PetScan::extract_access_expr(Expr
*expr
)
1091 struct pet_expr
*pe
;
1093 switch (expr
->getStmtClass()) {
1094 case Stmt::ArraySubscriptExprClass
:
1095 access
= extract_access(cast
<ArraySubscriptExpr
>(expr
));
1097 case Stmt::DeclRefExprClass
:
1098 access
= extract_access(cast
<DeclRefExpr
>(expr
));
1100 case Stmt::IntegerLiteralClass
:
1101 access
= extract_access(cast
<IntegerLiteral
>(expr
));
1108 pe
= pet_expr_from_access(access
);
1113 struct pet_expr
*PetScan::extract_expr(ParenExpr
*expr
)
1115 return extract_expr(expr
->getSubExpr());
1118 /* Construct a pet_expr representing a function call.
1120 * If we are passing along a pointer to an array element
1121 * or an entire row or even higher dimensional slice of an array,
1122 * then the function being called may write into the array.
1124 * We assume here that if the function is declared to take a pointer
1125 * to a const type, then the function will perform a read
1126 * and that otherwise, it will perform a write.
1128 struct pet_expr
*PetScan::extract_expr(CallExpr
*expr
)
1130 struct pet_expr
*res
= NULL
;
1134 fd
= expr
->getDirectCallee();
1140 name
= fd
->getDeclName().getAsString();
1141 res
= pet_expr_new_call(ctx
, name
.c_str(), expr
->getNumArgs());
1145 for (int i
= 0; i
< expr
->getNumArgs(); ++i
) {
1146 Expr
*arg
= expr
->getArg(i
);
1149 if (arg
->getStmtClass() == Stmt::ImplicitCastExprClass
) {
1150 ImplicitCastExpr
*ice
= cast
<ImplicitCastExpr
>(arg
);
1151 arg
= ice
->getSubExpr();
1153 if (arg
->getStmtClass() == Stmt::UnaryOperatorClass
) {
1154 UnaryOperator
*op
= cast
<UnaryOperator
>(arg
);
1155 if (op
->getOpcode() == UO_AddrOf
) {
1157 arg
= op
->getSubExpr();
1160 res
->args
[i
] = PetScan::extract_expr(arg
);
1163 if (arg
->getStmtClass() == Stmt::ArraySubscriptExprClass
&&
1164 array_depth(arg
->getType().getTypePtr()) > 0)
1166 if (is_addr
&& res
->args
[i
]->type
== pet_expr_access
) {
1167 ParmVarDecl
*parm
= fd
->getParamDecl(i
);
1168 if (!const_base(parm
->getType()))
1169 mark_write(res
->args
[i
]);
1179 /* Try and onstruct a pet_expr representing "expr".
1181 struct pet_expr
*PetScan::extract_expr(Expr
*expr
)
1183 switch (expr
->getStmtClass()) {
1184 case Stmt::UnaryOperatorClass
:
1185 return extract_expr(cast
<UnaryOperator
>(expr
));
1186 case Stmt::CompoundAssignOperatorClass
:
1187 case Stmt::BinaryOperatorClass
:
1188 return extract_expr(cast
<BinaryOperator
>(expr
));
1189 case Stmt::ImplicitCastExprClass
:
1190 return extract_expr(cast
<ImplicitCastExpr
>(expr
));
1191 case Stmt::ArraySubscriptExprClass
:
1192 case Stmt::DeclRefExprClass
:
1193 case Stmt::IntegerLiteralClass
:
1194 return extract_access_expr(expr
);
1195 case Stmt::FloatingLiteralClass
:
1196 return extract_expr(cast
<FloatingLiteral
>(expr
));
1197 case Stmt::ParenExprClass
:
1198 return extract_expr(cast
<ParenExpr
>(expr
));
1199 case Stmt::ConditionalOperatorClass
:
1200 return extract_expr(cast
<ConditionalOperator
>(expr
));
1201 case Stmt::CallExprClass
:
1202 return extract_expr(cast
<CallExpr
>(expr
));
1209 /* Check if the given initialization statement is an assignment.
1210 * If so, return that assignment. Otherwise return NULL.
1212 BinaryOperator
*PetScan::initialization_assignment(Stmt
*init
)
1214 BinaryOperator
*ass
;
1216 if (init
->getStmtClass() != Stmt::BinaryOperatorClass
)
1219 ass
= cast
<BinaryOperator
>(init
);
1220 if (ass
->getOpcode() != BO_Assign
)
1226 /* Check if the given initialization statement is a declaration
1227 * of a single variable.
1228 * If so, return that declaration. Otherwise return NULL.
1230 Decl
*PetScan::initialization_declaration(Stmt
*init
)
1234 if (init
->getStmtClass() != Stmt::DeclStmtClass
)
1237 decl
= cast
<DeclStmt
>(init
);
1239 if (!decl
->isSingleDecl())
1242 return decl
->getSingleDecl();
1245 /* Given the assignment operator in the initialization of a for loop,
1246 * extract the induction variable, i.e., the (integer)variable being
1249 ValueDecl
*PetScan::extract_induction_variable(BinaryOperator
*init
)
1256 lhs
= init
->getLHS();
1257 if (lhs
->getStmtClass() != Stmt::DeclRefExprClass
) {
1262 ref
= cast
<DeclRefExpr
>(lhs
);
1263 decl
= ref
->getDecl();
1264 type
= decl
->getType().getTypePtr();
1266 if (!type
->isIntegerType()) {
1274 /* Given the initialization statement of a for loop and the single
1275 * declaration in this initialization statement,
1276 * extract the induction variable, i.e., the (integer) variable being
1279 VarDecl
*PetScan::extract_induction_variable(Stmt
*init
, Decl
*decl
)
1283 vd
= cast
<VarDecl
>(decl
);
1285 const QualType type
= vd
->getType();
1286 if (!type
->isIntegerType()) {
1291 if (!vd
->getInit()) {
1299 /* Check that op is of the form iv++ or iv--.
1300 * "inc" is accordingly set to 1 or -1.
1302 bool PetScan::check_unary_increment(UnaryOperator
*op
, clang::ValueDecl
*iv
,
1308 if (!op
->isIncrementDecrementOp()) {
1313 if (op
->isIncrementOp())
1314 isl_int_set_si(inc
, 1);
1316 isl_int_set_si(inc
, -1);
1318 sub
= op
->getSubExpr();
1319 if (sub
->getStmtClass() != Stmt::DeclRefExprClass
) {
1324 ref
= cast
<DeclRefExpr
>(sub
);
1325 if (ref
->getDecl() != iv
) {
1333 /* If the isl_pw_aff on which isl_pw_aff_foreach_piece is called
1334 * has a single constant expression on a universe domain, then
1335 * put this constant in *user.
1337 static int extract_cst(__isl_take isl_set
*set
, __isl_take isl_aff
*aff
,
1340 isl_int
*inc
= (isl_int
*)user
;
1343 if (!isl_set_plain_is_universe(set
) || !isl_aff_is_cst(aff
))
1346 isl_aff_get_constant(aff
, inc
);
1354 /* Check if op is of the form
1358 * with inc a constant and set "inc" accordingly.
1360 * We extract an affine expression from the RHS and the subtract iv.
1361 * The result should be a constant.
1363 bool PetScan::check_binary_increment(BinaryOperator
*op
, clang::ValueDecl
*iv
,
1373 if (op
->getOpcode() != BO_Assign
) {
1379 if (lhs
->getStmtClass() != Stmt::DeclRefExprClass
) {
1384 ref
= cast
<DeclRefExpr
>(lhs
);
1385 if (ref
->getDecl() != iv
) {
1390 val
= extract_affine(op
->getRHS());
1392 id
= isl_id_alloc(ctx
, iv
->getName().str().c_str(), iv
);
1394 dim
= isl_space_set_alloc(ctx
, 1, 0);
1395 dim
= isl_space_set_dim_id(dim
, isl_dim_param
, 0, id
);
1396 aff
= isl_aff_zero_on_domain(isl_local_space_from_space(dim
));
1397 aff
= isl_aff_add_coefficient_si(aff
, isl_dim_param
, 0, 1);
1399 val
= isl_pw_aff_sub(val
, isl_pw_aff_from_aff(aff
));
1401 if (isl_pw_aff_foreach_piece(val
, &extract_cst
, &inc
) < 0) {
1402 isl_pw_aff_free(val
);
1407 isl_pw_aff_free(val
);
1412 /* Check that op is of the form iv += cst or iv -= cst.
1413 * "inc" is set to cst or -cst accordingly.
1415 bool PetScan::check_compound_increment(CompoundAssignOperator
*op
,
1416 clang::ValueDecl
*iv
, isl_int
&inc
)
1422 BinaryOperatorKind opcode
;
1424 opcode
= op
->getOpcode();
1425 if (opcode
!= BO_AddAssign
&& opcode
!= BO_SubAssign
) {
1429 if (opcode
== BO_SubAssign
)
1433 if (lhs
->getStmtClass() != Stmt::DeclRefExprClass
) {
1438 ref
= cast
<DeclRefExpr
>(lhs
);
1439 if (ref
->getDecl() != iv
) {
1446 if (rhs
->getStmtClass() == Stmt::UnaryOperatorClass
) {
1447 UnaryOperator
*op
= cast
<UnaryOperator
>(rhs
);
1448 if (op
->getOpcode() != UO_Minus
) {
1455 rhs
= op
->getSubExpr();
1458 if (rhs
->getStmtClass() != Stmt::IntegerLiteralClass
) {
1463 extract_int(cast
<IntegerLiteral
>(rhs
), &inc
);
1465 isl_int_neg(inc
, inc
);
1470 /* Check that the increment of the given for loop increments
1471 * (or decrements) the induction variable "iv".
1472 * "up" is set to true if the induction variable is incremented.
1474 bool PetScan::check_increment(ForStmt
*stmt
, ValueDecl
*iv
, isl_int
&v
)
1476 Stmt
*inc
= stmt
->getInc();
1483 if (inc
->getStmtClass() == Stmt::UnaryOperatorClass
)
1484 return check_unary_increment(cast
<UnaryOperator
>(inc
), iv
, v
);
1485 if (inc
->getStmtClass() == Stmt::CompoundAssignOperatorClass
)
1486 return check_compound_increment(
1487 cast
<CompoundAssignOperator
>(inc
), iv
, v
);
1488 if (inc
->getStmtClass() == Stmt::BinaryOperatorClass
)
1489 return check_binary_increment(cast
<BinaryOperator
>(inc
), iv
, v
);
1495 /* Embed the given iteration domain in an extra outer loop
1496 * with induction variable "var".
1497 * If this variable appeared as a parameter in the constraints,
1498 * it is replaced by the new outermost dimension.
1500 static __isl_give isl_set
*embed(__isl_take isl_set
*set
,
1501 __isl_take isl_id
*var
)
1505 set
= isl_set_insert_dims(set
, isl_dim_set
, 0, 1);
1506 pos
= isl_set_find_dim_by_id(set
, isl_dim_param
, var
);
1508 set
= isl_set_equate(set
, isl_dim_param
, pos
, isl_dim_set
, 0);
1509 set
= isl_set_project_out(set
, isl_dim_param
, pos
, 1);
1516 /* Construct a pet_scop for an infinite loop around the given body.
1518 * We extract a pet_scop for the body and then embed it in a loop with
1527 struct pet_scop
*PetScan::extract_infinite_loop(Stmt
*body
)
1533 struct pet_scop
*scop
;
1535 scop
= extract(body
);
1539 id
= isl_id_alloc(ctx
, "t", NULL
);
1540 domain
= isl_set_nat_universe(isl_space_set_alloc(ctx
, 0, 1));
1541 domain
= isl_set_set_dim_id(domain
, isl_dim_set
, 0, isl_id_copy(id
));
1542 dim
= isl_space_from_domain(isl_set_get_space(domain
));
1543 dim
= isl_space_add_dims(dim
, isl_dim_out
, 1);
1544 sched
= isl_map_universe(dim
);
1545 sched
= isl_map_equate(sched
, isl_dim_in
, 0, isl_dim_out
, 0);
1546 scop
= pet_scop_embed(scop
, domain
, sched
, id
);
1551 /* Construct a pet_scop for an infinite loop, i.e., a loop of the form
1557 struct pet_scop
*PetScan::extract_infinite_for(ForStmt
*stmt
)
1559 return extract_infinite_loop(stmt
->getBody());
1562 /* Check if the while loop is of the form
1567 * If so, construct a scop for an infinite loop around body.
1570 struct pet_scop
*PetScan::extract(WhileStmt
*stmt
)
1576 cond
= stmt
->getCond();
1582 set
= extract_condition(cond
);
1583 is_universe
= isl_set_plain_is_universe(set
);
1591 return extract_infinite_loop(stmt
->getBody());
1594 /* Check whether "cond" expresses a simple loop bound
1595 * on the only set dimension.
1596 * In particular, if "up" is set then "cond" should contain only
1597 * upper bounds on the set dimension.
1598 * Otherwise, it should contain only lower bounds.
1600 static bool is_simple_bound(__isl_keep isl_set
*cond
, isl_int inc
)
1602 if (isl_int_is_pos(inc
))
1603 return !isl_set_dim_has_lower_bound(cond
, isl_dim_set
, 0);
1605 return !isl_set_dim_has_upper_bound(cond
, isl_dim_set
, 0);
1608 /* Extend a condition on a given iteration of a loop to one that
1609 * imposes the same condition on all previous iterations.
1610 * "domain" expresses the lower [upper] bound on the iterations
1611 * when up is set [not set].
1613 * In particular, we construct the condition (when up is set)
1615 * forall i' : (domain(i') and i' <= i) => cond(i')
1617 * which is equivalent to
1619 * not exists i' : domain(i') and i' <= i and not cond(i')
1621 * We construct this set by negating cond, applying a map
1623 * { [i'] -> [i] : domain(i') and i' <= i }
1625 * and then negating the result again.
1627 static __isl_give isl_set
*valid_for_each_iteration(__isl_take isl_set
*cond
,
1628 __isl_take isl_set
*domain
, isl_int inc
)
1630 isl_map
*previous_to_this
;
1632 if (isl_int_is_pos(inc
))
1633 previous_to_this
= isl_map_lex_le(isl_set_get_space(domain
));
1635 previous_to_this
= isl_map_lex_ge(isl_set_get_space(domain
));
1637 previous_to_this
= isl_map_intersect_domain(previous_to_this
, domain
);
1639 cond
= isl_set_complement(cond
);
1640 cond
= isl_set_apply(cond
, previous_to_this
);
1641 cond
= isl_set_complement(cond
);
1646 /* Construct a domain of the form
1648 * [id] -> { [] : exists a: id = init + a * inc and a >= 0 }
1650 static __isl_give isl_set
*strided_domain(__isl_take isl_id
*id
,
1651 __isl_take isl_pw_aff
*init
, isl_int inc
)
1657 init
= isl_pw_aff_insert_dims(init
, isl_dim_in
, 0, 1);
1658 dim
= isl_pw_aff_get_domain_space(init
);
1659 aff
= isl_aff_zero_on_domain(isl_local_space_from_space(dim
));
1660 aff
= isl_aff_add_coefficient(aff
, isl_dim_in
, 0, inc
);
1661 init
= isl_pw_aff_add(init
, isl_pw_aff_from_aff(aff
));
1663 dim
= isl_space_set_alloc(isl_pw_aff_get_ctx(init
), 1, 1);
1664 dim
= isl_space_set_dim_id(dim
, isl_dim_param
, 0, id
);
1665 aff
= isl_aff_zero_on_domain(isl_local_space_from_space(dim
));
1666 aff
= isl_aff_add_coefficient_si(aff
, isl_dim_param
, 0, 1);
1668 set
= isl_pw_aff_eq_set(isl_pw_aff_from_aff(aff
), init
);
1670 set
= isl_set_lower_bound_si(set
, isl_dim_set
, 0, 0);
1672 return isl_set_project_out(set
, isl_dim_set
, 0, 1);
1675 static unsigned get_type_size(ValueDecl
*decl
)
1677 return decl
->getASTContext().getIntWidth(decl
->getType());
1680 /* Assuming "cond" represents a simple bound on a loop where the loop
1681 * iterator "iv" is incremented (or decremented) by one, check if wrapping
1684 * Under the given assumptions, wrapping is only possible if "cond" allows
1685 * for the last value before wrapping, i.e., 2^width - 1 in case of an
1686 * increasing iterator and 0 in case of a decreasing iterator.
1688 static bool can_wrap(__isl_keep isl_set
*cond
, ValueDecl
*iv
, isl_int inc
)
1694 test
= isl_set_copy(cond
);
1696 isl_int_init(limit
);
1697 if (isl_int_is_neg(inc
))
1698 isl_int_set_si(limit
, 0);
1700 isl_int_set_si(limit
, 1);
1701 isl_int_mul_2exp(limit
, limit
, get_type_size(iv
));
1702 isl_int_sub_ui(limit
, limit
, 1);
1705 test
= isl_set_fix(cond
, isl_dim_set
, 0, limit
);
1706 cw
= !isl_set_is_empty(test
);
1709 isl_int_clear(limit
);
1714 /* Given a one-dimensional space, construct the following mapping on this
1717 * { [v] -> [v mod 2^width] }
1719 * where width is the number of bits used to represent the values
1720 * of the unsigned variable "iv".
1722 static __isl_give isl_map
*compute_wrapping(__isl_take isl_space
*dim
,
1730 isl_int_set_si(mod
, 1);
1731 isl_int_mul_2exp(mod
, mod
, get_type_size(iv
));
1733 aff
= isl_aff_zero_on_domain(isl_local_space_from_space(dim
));
1734 aff
= isl_aff_add_coefficient_si(aff
, isl_dim_in
, 0, 1);
1735 aff
= isl_aff_mod(aff
, mod
);
1739 return isl_map_from_basic_map(isl_basic_map_from_aff(aff
));
1740 map
= isl_map_reverse(map
);
1743 /* Construct a pet_scop for a for statement.
1744 * The for loop is required to be of the form
1746 * for (i = init; condition; ++i)
1750 * for (i = init; condition; --i)
1752 * The initialization of the for loop should either be an assignment
1753 * to an integer variable, or a declaration of such a variable with
1756 * We extract a pet_scop for the body and then embed it in a loop with
1757 * iteration domain and schedule
1759 * { [i] : i >= init and condition' }
1764 * { [i] : i <= init and condition' }
1767 * Where condition' is equal to condition if the latter is
1768 * a simple upper [lower] bound and a condition that is extended
1769 * to apply to all previous iterations otherwise.
1771 * If the stride of the loop is not 1, then "i >= init" is replaced by
1773 * (exists a: i = init + stride * a and a >= 0)
1775 * If the loop iterator i is unsigned, then wrapping may occur.
1776 * During the computation, we work with a virtual iterator that
1777 * does not wrap. However, the condition in the code applies
1778 * to the wrapped value, so we need to change condition(i)
1779 * into condition([i % 2^width]).
1780 * After computing the virtual domain and schedule, we apply
1781 * the function { [v] -> [v % 2^width] } to the domain and the domain
1782 * of the schedule. In order not to lose any information, we also
1783 * need to intersect the domain of the schedule with the virtual domain
1784 * first, since some iterations in the wrapped domain may be scheduled
1785 * several times, typically an infinite number of times.
1786 * Note that there is no need to perform this final wrapping
1787 * if the loop condition (after wrapping) is simple.
1789 * Wrapping on unsigned iterators can be avoided entirely if
1790 * loop condition is simple, the loop iterator is incremented
1791 * [decremented] by one and the last value before wrapping cannot
1792 * possibly satisfy the loop condition.
1794 * Before extracting a pet_scop from the body we remove all
1795 * assignments in assigned_value to variables that are assigned
1796 * somewhere in the body of the loop.
1798 struct pet_scop
*PetScan::extract_for(ForStmt
*stmt
)
1800 BinaryOperator
*ass
;
1810 struct pet_scop
*scop
;
1811 assigned_value_cache
cache(assigned_value
);
1816 isl_map
*wrap
= NULL
;
1818 if (!stmt
->getInit() && !stmt
->getCond() && !stmt
->getInc())
1819 return extract_infinite_for(stmt
);
1821 init
= stmt
->getInit();
1826 if ((ass
= initialization_assignment(init
)) != NULL
) {
1827 iv
= extract_induction_variable(ass
);
1830 lhs
= ass
->getLHS();
1831 rhs
= ass
->getRHS();
1832 } else if ((decl
= initialization_declaration(init
)) != NULL
) {
1833 VarDecl
*var
= extract_induction_variable(init
, decl
);
1837 rhs
= var
->getInit();
1838 lhs
= DeclRefExpr::Create(iv
->getASTContext(),
1839 var
->getQualifierLoc(), iv
, var
->getInnerLocStart(),
1840 var
->getType(), VK_LValue
);
1842 unsupported(stmt
->getInit());
1847 if (!check_increment(stmt
, iv
, inc
)) {
1852 is_unsigned
= iv
->getType()->isUnsignedIntegerType();
1854 assigned_value
[iv
] = NULL
;
1855 clear_assignments
clear(assigned_value
);
1856 clear
.TraverseStmt(stmt
->getBody());
1858 id
= isl_id_alloc(ctx
, iv
->getName().str().c_str(), iv
);
1860 is_one
= isl_int_is_one(inc
) || isl_int_is_negone(inc
);
1862 domain
= extract_comparison(isl_int_is_pos(inc
) ? BO_GE
: BO_LE
,
1865 isl_pw_aff
*lb
= extract_affine(rhs
);
1866 domain
= strided_domain(isl_id_copy(id
), lb
, inc
);
1869 cond
= extract_condition(stmt
->getCond());
1870 cond
= embed(cond
, isl_id_copy(id
));
1871 domain
= embed(domain
, isl_id_copy(id
));
1872 is_simple
= is_simple_bound(cond
, inc
);
1874 (!is_simple
|| !is_one
|| can_wrap(cond
, iv
, inc
))) {
1875 wrap
= compute_wrapping(isl_set_get_space(cond
), iv
);
1876 cond
= isl_set_apply(cond
, isl_map_reverse(isl_map_copy(wrap
)));
1877 is_simple
= is_simple
&& is_simple_bound(cond
, inc
);
1880 cond
= valid_for_each_iteration(cond
,
1881 isl_set_copy(domain
), inc
);
1882 domain
= isl_set_intersect(domain
, cond
);
1883 domain
= isl_set_set_dim_id(domain
, isl_dim_set
, 0, isl_id_copy(id
));
1884 dim
= isl_space_from_domain(isl_set_get_space(domain
));
1885 dim
= isl_space_add_dims(dim
, isl_dim_out
, 1);
1886 sched
= isl_map_universe(dim
);
1887 if (isl_int_is_pos(inc
))
1888 sched
= isl_map_equate(sched
, isl_dim_in
, 0, isl_dim_out
, 0);
1890 sched
= isl_map_oppose(sched
, isl_dim_in
, 0, isl_dim_out
, 0);
1892 if (is_unsigned
&& !is_simple
) {
1893 wrap
= isl_map_set_dim_id(wrap
,
1894 isl_dim_out
, 0, isl_id_copy(id
));
1895 sched
= isl_map_intersect_domain(sched
, isl_set_copy(domain
));
1896 domain
= isl_set_apply(domain
, isl_map_copy(wrap
));
1897 sched
= isl_map_apply_domain(sched
, wrap
);
1901 scop
= extract(stmt
->getBody());
1902 scop
= pet_scop_embed(scop
, domain
, sched
, id
);
1908 struct pet_scop
*PetScan::extract(CompoundStmt
*stmt
)
1910 return extract(stmt
->children());
1913 /* Look for parameters in any access relation in "expr" that
1914 * refer to non-affine constructs. In particular, these are
1915 * parameters with no name.
1917 * If there are any such parameters, then the domain of the access
1918 * relation, which is still [] at this point, is replaced by
1919 * [[] -> [t_1,...,t_n]], with n the number of these parameters
1920 * (after identifying identical non-affine constructs).
1921 * The parameters are then equated to the corresponding t dimensions
1922 * and subsequently projected out.
1923 * param2pos maps the position of the parameter to the position
1924 * of the corresponding t dimension.
1926 struct pet_expr
*PetScan::resolve_nested(struct pet_expr
*expr
)
1933 std::map
<int,int> param2pos
;
1938 for (int i
= 0; i
< expr
->n_arg
; ++i
) {
1939 expr
->args
[i
] = resolve_nested(expr
->args
[i
]);
1940 if (!expr
->args
[i
]) {
1941 pet_expr_free(expr
);
1946 if (expr
->type
!= pet_expr_access
)
1949 nparam
= isl_map_dim(expr
->acc
.access
, isl_dim_param
);
1951 for (int i
= 0; i
< nparam
; ++i
) {
1952 isl_id
*id
= isl_map_get_dim_id(expr
->acc
.access
,
1954 if (id
&& isl_id_get_user(id
) && !isl_id_get_name(id
))
1963 expr
->args
= isl_calloc_array(ctx
, struct pet_expr
*, n
);
1967 n_in
= isl_map_dim(expr
->acc
.access
, isl_dim_in
);
1968 for (int i
= 0, pos
= 0; i
< nparam
; ++i
) {
1970 isl_id
*id
= isl_map_get_dim_id(expr
->acc
.access
,
1974 if (!(id
&& isl_id_get_user(id
) && !isl_id_get_name(id
))) {
1979 nested
= (Expr
*) isl_id_get_user(id
);
1980 expr
->args
[pos
] = extract_expr(nested
);
1982 for (j
= 0; j
< pos
; ++j
)
1983 if (pet_expr_is_equal(expr
->args
[j
], expr
->args
[pos
]))
1987 pet_expr_free(expr
->args
[pos
]);
1988 param2pos
[i
] = n_in
+ j
;
1991 param2pos
[i
] = n_in
+ pos
++;
1997 dim
= isl_map_get_space(expr
->acc
.access
);
1998 dim
= isl_space_domain(dim
);
1999 dim
= isl_space_from_domain(dim
);
2000 dim
= isl_space_add_dims(dim
, isl_dim_out
, n
);
2001 map
= isl_map_universe(dim
);
2002 map
= isl_map_domain_map(map
);
2003 map
= isl_map_reverse(map
);
2004 expr
->acc
.access
= isl_map_apply_domain(expr
->acc
.access
, map
);
2006 for (int i
= nparam
- 1; i
>= 0; --i
) {
2007 isl_id
*id
= isl_map_get_dim_id(expr
->acc
.access
,
2009 if (!(id
&& isl_id_get_user(id
) && !isl_id_get_name(id
))) {
2014 expr
->acc
.access
= isl_map_equate(expr
->acc
.access
,
2015 isl_dim_param
, i
, isl_dim_in
,
2017 expr
->acc
.access
= isl_map_project_out(expr
->acc
.access
,
2018 isl_dim_param
, i
, 1);
2025 pet_expr_free(expr
);
2029 /* Convert a top-level pet_expr to a pet_scop with one statement.
2030 * This mainly involves resolving nested expression parameters
2031 * and setting the name of the iteration space.
2033 struct pet_scop
*PetScan::extract(Stmt
*stmt
, struct pet_expr
*expr
)
2035 struct pet_stmt
*ps
;
2036 SourceLocation loc
= stmt
->getLocStart();
2037 int line
= PP
.getSourceManager().getExpansionLineNumber(loc
);
2039 expr
= resolve_nested(expr
);
2040 ps
= pet_stmt_from_pet_expr(ctx
, line
, n_stmt
++, expr
);
2041 return pet_scop_from_pet_stmt(ctx
, ps
);
2044 /* Check whether "expr" is an affine expression.
2045 * We turn on autodetection so that we won't generate any warnings
2046 * and turn off nesting, so that we won't accept any non-affine constructs.
2048 bool PetScan::is_affine(Expr
*expr
)
2051 int save_autodetect
= autodetect
;
2052 bool save_nesting
= nesting_enabled
;
2055 nesting_enabled
= false;
2057 pwaff
= extract_affine(expr
);
2058 isl_pw_aff_free(pwaff
);
2060 autodetect
= save_autodetect
;
2061 nesting_enabled
= save_nesting
;
2063 return pwaff
!= NULL
;
2066 /* Check whether "expr" is an affine constraint.
2067 * We turn on autodetection so that we won't generate any warnings
2068 * and turn off nesting, so that we won't accept any non-affine constructs.
2070 bool PetScan::is_affine_condition(Expr
*expr
)
2073 int save_autodetect
= autodetect
;
2074 bool save_nesting
= nesting_enabled
;
2077 nesting_enabled
= false;
2079 set
= extract_condition(expr
);
2082 autodetect
= save_autodetect
;
2083 nesting_enabled
= save_nesting
;
2088 /* If the top-level expression of "stmt" is an assignment, then
2089 * return that assignment as a BinaryOperator.
2090 * Otherwise return NULL.
2092 static BinaryOperator
*top_assignment_or_null(Stmt
*stmt
)
2094 BinaryOperator
*ass
;
2098 if (stmt
->getStmtClass() != Stmt::BinaryOperatorClass
)
2101 ass
= cast
<BinaryOperator
>(stmt
);
2102 if(ass
->getOpcode() != BO_Assign
)
2108 /* Check if the given if statement is a conditional assignement
2109 * with a non-affine condition. If so, construct a pet_scop
2110 * corresponding to this conditional assignment. Otherwise return NULL.
2112 * In particular we check if "stmt" is of the form
2119 * where a is some array or scalar access.
2120 * The constructed pet_scop then corresponds to the expression
2122 * a = condition ? f(...) : g(...)
2124 * All access relations in f(...) are intersected with condition
2125 * while all access relation in g(...) are intersected with the complement.
2127 struct pet_scop
*PetScan::extract_conditional_assignment(IfStmt
*stmt
)
2129 BinaryOperator
*ass_then
, *ass_else
;
2130 isl_map
*write_then
, *write_else
;
2131 isl_set
*cond
, *comp
;
2132 isl_map
*map
, *map_true
, *map_false
;
2134 struct pet_expr
*pe_cond
, *pe_then
, *pe_else
, *pe
, *pe_write
;
2135 bool save_nesting
= nesting_enabled
;
2137 ass_then
= top_assignment_or_null(stmt
->getThen());
2138 ass_else
= top_assignment_or_null(stmt
->getElse());
2140 if (!ass_then
|| !ass_else
)
2143 if (is_affine_condition(stmt
->getCond()))
2146 write_then
= extract_access(ass_then
->getLHS());
2147 write_else
= extract_access(ass_else
->getLHS());
2149 equal
= isl_map_is_equal(write_then
, write_else
);
2150 isl_map_free(write_else
);
2151 if (equal
< 0 || !equal
) {
2152 isl_map_free(write_then
);
2156 nesting_enabled
= allow_nested
;
2157 cond
= extract_condition(stmt
->getCond());
2158 nesting_enabled
= save_nesting
;
2159 comp
= isl_set_complement(isl_set_copy(cond
));
2160 map_true
= isl_map_from_domain(isl_set_copy(cond
));
2161 map_true
= isl_map_add_dims(map_true
, isl_dim_out
, 1);
2162 map_true
= isl_map_fix_si(map_true
, isl_dim_out
, 0, 1);
2163 map_false
= isl_map_from_domain(isl_set_copy(comp
));
2164 map_false
= isl_map_add_dims(map_false
, isl_dim_out
, 1);
2165 map_false
= isl_map_fix_si(map_false
, isl_dim_out
, 0, 0);
2166 map
= isl_map_union_disjoint(map_true
, map_false
);
2168 pe_cond
= pet_expr_from_access(map
);
2170 pe_then
= extract_expr(ass_then
->getRHS());
2171 pe_then
= pet_expr_restrict(pe_then
, cond
);
2172 pe_else
= extract_expr(ass_else
->getRHS());
2173 pe_else
= pet_expr_restrict(pe_else
, comp
);
2175 pe
= pet_expr_new_ternary(ctx
, pe_cond
, pe_then
, pe_else
);
2176 pe_write
= pet_expr_from_access(write_then
);
2178 pe_write
->acc
.write
= 1;
2179 pe_write
->acc
.read
= 0;
2181 pe
= pet_expr_new_binary(ctx
, pet_op_assign
, pe_write
, pe
);
2182 return extract(stmt
, pe
);
2185 /* Construct a pet_scop for an if statement.
2187 struct pet_scop
*PetScan::extract(IfStmt
*stmt
)
2190 struct pet_scop
*scop_then
, *scop_else
, *scop
;
2191 assigned_value_cache
cache(assigned_value
);
2193 scop
= extract_conditional_assignment(stmt
);
2197 scop_then
= extract(stmt
->getThen());
2199 if (stmt
->getElse()) {
2200 scop_else
= extract(stmt
->getElse());
2202 if (scop_then
&& !scop_else
) {
2206 if (!scop_then
&& scop_else
) {
2213 cond
= extract_condition(stmt
->getCond());
2214 scop
= pet_scop_restrict(scop_then
, isl_set_copy(cond
));
2216 if (stmt
->getElse()) {
2217 cond
= isl_set_complement(cond
);
2218 scop_else
= pet_scop_restrict(scop_else
, cond
);
2219 scop
= pet_scop_add(ctx
, scop
, scop_else
);
2226 /* Try and construct a pet_scop corresponding to "stmt".
2228 struct pet_scop
*PetScan::extract(Stmt
*stmt
)
2230 if (isa
<Expr
>(stmt
))
2231 return extract(stmt
, extract_expr(cast
<Expr
>(stmt
)));
2233 switch (stmt
->getStmtClass()) {
2234 case Stmt::WhileStmtClass
:
2235 return extract(cast
<WhileStmt
>(stmt
));
2236 case Stmt::ForStmtClass
:
2237 return extract_for(cast
<ForStmt
>(stmt
));
2238 case Stmt::IfStmtClass
:
2239 return extract(cast
<IfStmt
>(stmt
));
2240 case Stmt::CompoundStmtClass
:
2241 return extract(cast
<CompoundStmt
>(stmt
));
2249 /* Try and construct a pet_scop corresponding to (part of)
2250 * a sequence of statements.
2252 struct pet_scop
*PetScan::extract(StmtRange stmt_range
)
2257 bool partial_range
= false;
2259 scop
= pet_scop_empty(ctx
);
2260 for (i
= stmt_range
.first
, j
= 0; i
!= stmt_range
.second
; ++i
, ++j
) {
2262 struct pet_scop
*scop_i
;
2263 scop_i
= extract(child
);
2264 if (scop
&& partial
) {
2265 pet_scop_free(scop_i
);
2268 scop_i
= pet_scop_prefix(scop_i
, j
);
2271 scop
= pet_scop_add(ctx
, scop
, scop_i
);
2273 partial_range
= true;
2274 if (scop
->n_stmt
!= 0 && !scop_i
)
2277 scop
= pet_scop_add(ctx
, scop
, scop_i
);
2283 if (scop
&& partial_range
)
2289 /* Check if the scop marked by the user is exactly this Stmt
2290 * or part of this Stmt.
2291 * If so, return a pet_scop corresponding to the marked region.
2292 * Otherwise, return NULL.
2294 struct pet_scop
*PetScan::scan(Stmt
*stmt
)
2296 SourceManager
&SM
= PP
.getSourceManager();
2297 unsigned start_off
, end_off
;
2299 start_off
= SM
.getFileOffset(stmt
->getLocStart());
2300 end_off
= SM
.getFileOffset(stmt
->getLocEnd());
2302 if (start_off
> loc
.end
)
2304 if (end_off
< loc
.start
)
2306 if (start_off
>= loc
.start
&& end_off
<= loc
.end
) {
2307 return extract(stmt
);
2311 for (start
= stmt
->child_begin(); start
!= stmt
->child_end(); ++start
) {
2312 Stmt
*child
= *start
;
2313 start_off
= SM
.getFileOffset(child
->getLocStart());
2314 end_off
= SM
.getFileOffset(child
->getLocEnd());
2315 if (start_off
< loc
.start
&& end_off
> loc
.end
)
2317 if (start_off
>= loc
.start
)
2322 for (end
= start
; end
!= stmt
->child_end(); ++end
) {
2324 start_off
= SM
.getFileOffset(child
->getLocStart());
2325 if (start_off
>= loc
.end
)
2329 return extract(StmtRange(start
, end
));
2332 /* Set the size of index "pos" of "array" to "size".
2333 * In particular, add a constraint of the form
2337 * to array->extent and a constraint of the form
2341 * to array->context.
2343 static struct pet_array
*update_size(struct pet_array
*array
, int pos
,
2344 __isl_take isl_pw_aff
*size
)
2354 valid
= isl_pw_aff_nonneg_set(isl_pw_aff_copy(size
));
2355 array
->context
= isl_set_intersect(array
->context
, valid
);
2357 dim
= isl_set_get_space(array
->extent
);
2358 aff
= isl_aff_zero_on_domain(isl_local_space_from_space(dim
));
2359 aff
= isl_aff_add_coefficient_si(aff
, isl_dim_in
, pos
, 1);
2360 univ
= isl_set_universe(isl_aff_get_domain_space(aff
));
2361 index
= isl_pw_aff_alloc(univ
, aff
);
2363 size
= isl_pw_aff_add_dims(size
, isl_dim_in
,
2364 isl_set_dim(array
->extent
, isl_dim_set
));
2365 id
= isl_set_get_tuple_id(array
->extent
);
2366 size
= isl_pw_aff_set_tuple_id(size
, id
);
2367 bound
= isl_pw_aff_lt_set(index
, size
);
2369 array
->extent
= isl_set_intersect(array
->extent
, bound
);
2371 if (!array
->context
|| !array
->extent
)
2376 pet_array_free(array
);
2380 /* Figure out the size of the array at position "pos" and all
2381 * subsequent positions from "type" and update "array" accordingly.
2383 struct pet_array
*PetScan::set_upper_bounds(struct pet_array
*array
,
2384 const Type
*type
, int pos
)
2386 const ArrayType
*atype
;
2392 if (type
->isPointerType()) {
2393 type
= type
->getPointeeType().getTypePtr();
2394 return set_upper_bounds(array
, type
, pos
+ 1);
2396 if (!type
->isArrayType())
2399 type
= type
->getCanonicalTypeInternal().getTypePtr();
2400 atype
= cast
<ArrayType
>(type
);
2402 if (type
->isConstantArrayType()) {
2403 const ConstantArrayType
*ca
= cast
<ConstantArrayType
>(atype
);
2404 size
= extract_affine(ca
->getSize());
2405 array
= update_size(array
, pos
, size
);
2406 } else if (type
->isVariableArrayType()) {
2407 const VariableArrayType
*vla
= cast
<VariableArrayType
>(atype
);
2408 size
= extract_affine(vla
->getSizeExpr());
2409 array
= update_size(array
, pos
, size
);
2412 type
= atype
->getElementType().getTypePtr();
2414 return set_upper_bounds(array
, type
, pos
+ 1);
2417 /* Construct and return a pet_array corresponding to the variable "decl".
2418 * In particular, initialize array->extent to
2420 * { name[i_1,...,i_d] : i_1,...,i_d >= 0 }
2422 * and then call set_upper_bounds to set the upper bounds on the indices
2423 * based on the type of the variable.
2425 struct pet_array
*PetScan::extract_array(isl_ctx
*ctx
, ValueDecl
*decl
)
2427 struct pet_array
*array
;
2428 QualType qt
= decl
->getType();
2429 const Type
*type
= qt
.getTypePtr();
2430 int depth
= array_depth(type
);
2431 QualType base
= base_type(qt
);
2436 array
= isl_calloc_type(ctx
, struct pet_array
);
2440 id
= isl_id_alloc(ctx
, decl
->getName().str().c_str(), decl
);
2441 dim
= isl_space_set_alloc(ctx
, 0, depth
);
2442 dim
= isl_space_set_tuple_id(dim
, isl_dim_set
, id
);
2444 array
->extent
= isl_set_nat_universe(dim
);
2446 dim
= isl_space_params_alloc(ctx
, 0);
2447 array
->context
= isl_set_universe(dim
);
2449 array
= set_upper_bounds(array
, type
, 0);
2453 name
= base
.getAsString();
2454 array
->element_type
= strdup(name
.c_str());
2459 /* Construct a list of pet_arrays, one for each array (or scalar)
2460 * accessed inside "scop" add this list to "scop" and return the result.
2462 * The context of "scop" is updated with the intesection of
2463 * the contexts of all arrays, i.e., constraints on the parameters
2464 * that ensure that the arrays have a valid (non-negative) size.
2466 struct pet_scop
*PetScan::scan_arrays(struct pet_scop
*scop
)
2469 set
<ValueDecl
*> arrays
;
2470 set
<ValueDecl
*>::iterator it
;
2475 pet_scop_collect_arrays(scop
, arrays
);
2477 scop
->n_array
= arrays
.size();
2478 if (scop
->n_array
== 0)
2481 scop
->arrays
= isl_calloc_array(ctx
, struct pet_array
*, scop
->n_array
);
2485 for (it
= arrays
.begin(), i
= 0; it
!= arrays
.end(); ++it
, ++i
) {
2486 struct pet_array
*array
;
2487 scop
->arrays
[i
] = array
= extract_array(ctx
, *it
);
2488 if (!scop
->arrays
[i
])
2490 scop
->context
= isl_set_intersect(scop
->context
,
2491 isl_set_copy(array
->context
));
2498 pet_scop_free(scop
);
2502 /* Construct a pet_scop from the given function.
2504 struct pet_scop
*PetScan::scan(FunctionDecl
*fd
)
2509 stmt
= fd
->getBody();
2512 scop
= extract(stmt
);
2515 scop
= pet_scop_detect_parameter_accesses(scop
);
2516 scop
= scan_arrays(scop
);