mark __pet_test_* variables as uniquely_defined
[pet.git] / scan.cc
blob7e5842b9b06b4f005730ab82e4c52ad0bc96b9a3
1 /*
2 * Copyright 2011 Leiden University. All rights reserved.
3 * Copyright 2012 Ecole Normale Superieure. All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 *
9 * 1. Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
12 * 2. Redistributions in binary form must reproduce the above
13 * copyright notice, this list of conditions and the following
14 * disclaimer in the documentation and/or other materials provided
15 * with the distribution.
17 * THIS SOFTWARE IS PROVIDED BY LEIDEN UNIVERSITY ''AS IS'' AND ANY
18 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
20 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL LEIDEN UNIVERSITY OR
21 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
22 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
23 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA,
24 * OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
25 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
26 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
27 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29 * The views and conclusions contained in the software and documentation
30 * are those of the authors and should not be interpreted as
31 * representing official policies, either expressed or implied, of
32 * Leiden University.
33 */
35 #include <set>
36 #include <map>
37 #include <iostream>
38 #include <clang/AST/ASTDiagnostic.h>
39 #include <clang/AST/Expr.h>
40 #include <clang/AST/RecursiveASTVisitor.h>
42 #include <isl/id.h>
43 #include <isl/space.h>
44 #include <isl/aff.h>
45 #include <isl/set.h>
47 #include "options.h"
48 #include "scan.h"
49 #include "scop.h"
50 #include "scop_plus.h"
52 #include "config.h"
54 using namespace std;
55 using namespace clang;
57 #if defined(DECLREFEXPR_CREATE_REQUIRES_BOOL)
58 static DeclRefExpr *create_DeclRefExpr(VarDecl *var)
60 return DeclRefExpr::Create(var->getASTContext(), var->getQualifierLoc(),
61 SourceLocation(), var, false, var->getInnerLocStart(),
62 var->getType(), VK_LValue);
64 #elif defined(DECLREFEXPR_CREATE_REQUIRES_SOURCELOCATION)
65 static DeclRefExpr *create_DeclRefExpr(VarDecl *var)
67 return DeclRefExpr::Create(var->getASTContext(), var->getQualifierLoc(),
68 SourceLocation(), var, var->getInnerLocStart(), var->getType(),
69 VK_LValue);
71 #else
72 static DeclRefExpr *create_DeclRefExpr(VarDecl *var)
74 return DeclRefExpr::Create(var->getASTContext(), var->getQualifierLoc(),
75 var, var->getInnerLocStart(), var->getType(), VK_LValue);
77 #endif
79 /* Check if the element type corresponding to the given array type
80 * has a const qualifier.
82 static bool const_base(QualType qt)
84 const Type *type = qt.getTypePtr();
86 if (type->isPointerType())
87 return const_base(type->getPointeeType());
88 if (type->isArrayType()) {
89 const ArrayType *atype;
90 type = type->getCanonicalTypeInternal().getTypePtr();
91 atype = cast<ArrayType>(type);
92 return const_base(atype->getElementType());
95 return qt.isConstQualified();
98 /* Mark "decl" as having an unknown value in "assigned_value".
100 * If no (known or unknown) value was assigned to "decl" before,
101 * then it may have been treated as a parameter before and may
102 * therefore appear in a value assigned to another variable.
103 * If so, this assignment needs to be turned into an unknown value too.
105 static void clear_assignment(map<ValueDecl *, isl_pw_aff *> &assigned_value,
106 ValueDecl *decl)
108 map<ValueDecl *, isl_pw_aff *>::iterator it;
110 it = assigned_value.find(decl);
112 assigned_value[decl] = NULL;
114 if (it == assigned_value.end())
115 return;
117 for (it = assigned_value.begin(); it != assigned_value.end(); ++it) {
118 isl_pw_aff *pa = it->second;
119 int nparam = isl_pw_aff_dim(pa, isl_dim_param);
121 for (int i = 0; i < nparam; ++i) {
122 isl_id *id;
124 if (!isl_pw_aff_has_dim_id(pa, isl_dim_param, i))
125 continue;
126 id = isl_pw_aff_get_dim_id(pa, isl_dim_param, i);
127 if (isl_id_get_user(id) == decl)
128 it->second = NULL;
129 isl_id_free(id);
134 /* Look for any assignments to scalar variables in part of the parse
135 * tree and set assigned_value to NULL for each of them.
136 * Also reset assigned_value if the address of a scalar variable
137 * is being taken. As an exception, if the address is passed to a function
138 * that is declared to receive a const pointer, then assigned_value is
139 * not reset.
141 * This ensures that we won't use any previously stored value
142 * in the current subtree and its parents.
144 struct clear_assignments : RecursiveASTVisitor<clear_assignments> {
145 map<ValueDecl *, isl_pw_aff *> &assigned_value;
146 set<UnaryOperator *> skip;
148 clear_assignments(map<ValueDecl *, isl_pw_aff *> &assigned_value) :
149 assigned_value(assigned_value) {}
151 /* Check for "address of" operators whose value is passed
152 * to a const pointer argument and add them to "skip", so that
153 * we can skip them in VisitUnaryOperator.
155 bool VisitCallExpr(CallExpr *expr) {
156 FunctionDecl *fd;
157 fd = expr->getDirectCallee();
158 if (!fd)
159 return true;
160 for (int i = 0; i < expr->getNumArgs(); ++i) {
161 Expr *arg = expr->getArg(i);
162 UnaryOperator *op;
163 if (arg->getStmtClass() == Stmt::ImplicitCastExprClass) {
164 ImplicitCastExpr *ice;
165 ice = cast<ImplicitCastExpr>(arg);
166 arg = ice->getSubExpr();
168 if (arg->getStmtClass() != Stmt::UnaryOperatorClass)
169 continue;
170 op = cast<UnaryOperator>(arg);
171 if (op->getOpcode() != UO_AddrOf)
172 continue;
173 if (const_base(fd->getParamDecl(i)->getType()))
174 skip.insert(op);
176 return true;
179 bool VisitUnaryOperator(UnaryOperator *expr) {
180 Expr *arg;
181 DeclRefExpr *ref;
182 ValueDecl *decl;
184 if (expr->getOpcode() != UO_AddrOf)
185 return true;
186 if (skip.find(expr) != skip.end())
187 return true;
189 arg = expr->getSubExpr();
190 if (arg->getStmtClass() != Stmt::DeclRefExprClass)
191 return true;
192 ref = cast<DeclRefExpr>(arg);
193 decl = ref->getDecl();
194 clear_assignment(assigned_value, decl);
195 return true;
198 bool VisitBinaryOperator(BinaryOperator *expr) {
199 Expr *lhs;
200 DeclRefExpr *ref;
201 ValueDecl *decl;
203 if (!expr->isAssignmentOp())
204 return true;
205 lhs = expr->getLHS();
206 if (lhs->getStmtClass() != Stmt::DeclRefExprClass)
207 return true;
208 ref = cast<DeclRefExpr>(lhs);
209 decl = ref->getDecl();
210 clear_assignment(assigned_value, decl);
211 return true;
215 /* Keep a copy of the currently assigned values.
217 * Any variable that is assigned a value inside the current scope
218 * is removed again when we leave the scope (either because it wasn't
219 * stored in the cache or because it has a different value in the cache).
221 struct assigned_value_cache {
222 map<ValueDecl *, isl_pw_aff *> &assigned_value;
223 map<ValueDecl *, isl_pw_aff *> cache;
225 assigned_value_cache(map<ValueDecl *, isl_pw_aff *> &assigned_value) :
226 assigned_value(assigned_value), cache(assigned_value) {}
227 ~assigned_value_cache() {
228 map<ValueDecl *, isl_pw_aff *>::iterator it = cache.begin();
229 for (it = assigned_value.begin(); it != assigned_value.end();
230 ++it) {
231 if (!it->second ||
232 (cache.find(it->first) != cache.end() &&
233 cache[it->first] != it->second))
234 cache[it->first] = NULL;
236 assigned_value = cache;
240 /* Insert an expression into the collection of expressions,
241 * provided it is not already in there.
242 * The isl_pw_affs are freed in the destructor.
244 void PetScan::insert_expression(__isl_take isl_pw_aff *expr)
246 std::set<isl_pw_aff *>::iterator it;
248 if (expressions.find(expr) == expressions.end())
249 expressions.insert(expr);
250 else
251 isl_pw_aff_free(expr);
254 PetScan::~PetScan()
256 std::set<isl_pw_aff *>::iterator it;
258 for (it = expressions.begin(); it != expressions.end(); ++it)
259 isl_pw_aff_free(*it);
261 isl_union_map_free(value_bounds);
264 /* Called if we found something we (currently) cannot handle.
265 * We'll provide more informative warnings later.
267 * We only actually complain if autodetect is false.
269 void PetScan::unsupported(Stmt *stmt, const char *msg)
271 if (options->autodetect)
272 return;
274 SourceLocation loc = stmt->getLocStart();
275 DiagnosticsEngine &diag = PP.getDiagnostics();
276 unsigned id = diag.getCustomDiagID(DiagnosticsEngine::Warning,
277 msg ? msg : "unsupported");
278 DiagnosticBuilder B = diag.Report(loc, id) << stmt->getSourceRange();
281 /* Extract an integer from "expr" and store it in "v".
283 int PetScan::extract_int(IntegerLiteral *expr, isl_int *v)
285 const Type *type = expr->getType().getTypePtr();
286 int is_signed = type->hasSignedIntegerRepresentation();
288 if (is_signed) {
289 int64_t i = expr->getValue().getSExtValue();
290 isl_int_set_si(*v, i);
291 } else {
292 uint64_t i = expr->getValue().getZExtValue();
293 isl_int_set_ui(*v, i);
296 return 0;
299 /* Extract an integer from "expr" and store it in "v".
300 * Return -1 if "expr" does not (obviously) represent an integer.
302 int PetScan::extract_int(clang::ParenExpr *expr, isl_int *v)
304 return extract_int(expr->getSubExpr(), v);
307 /* Extract an integer from "expr" and store it in "v".
308 * Return -1 if "expr" does not (obviously) represent an integer.
310 int PetScan::extract_int(clang::Expr *expr, isl_int *v)
312 if (expr->getStmtClass() == Stmt::IntegerLiteralClass)
313 return extract_int(cast<IntegerLiteral>(expr), v);
314 if (expr->getStmtClass() == Stmt::ParenExprClass)
315 return extract_int(cast<ParenExpr>(expr), v);
317 unsupported(expr);
318 return -1;
321 /* Extract an affine expression from the IntegerLiteral "expr".
323 __isl_give isl_pw_aff *PetScan::extract_affine(IntegerLiteral *expr)
325 isl_space *dim = isl_space_params_alloc(ctx, 0);
326 isl_local_space *ls = isl_local_space_from_space(isl_space_copy(dim));
327 isl_aff *aff = isl_aff_zero_on_domain(ls);
328 isl_set *dom = isl_set_universe(dim);
329 isl_int v;
331 isl_int_init(v);
332 extract_int(expr, &v);
333 aff = isl_aff_add_constant(aff, v);
334 isl_int_clear(v);
336 return isl_pw_aff_alloc(dom, aff);
339 /* Extract an affine expression from the APInt "val".
341 __isl_give isl_pw_aff *PetScan::extract_affine(const llvm::APInt &val)
343 isl_space *dim = isl_space_params_alloc(ctx, 0);
344 isl_local_space *ls = isl_local_space_from_space(isl_space_copy(dim));
345 isl_aff *aff = isl_aff_zero_on_domain(ls);
346 isl_set *dom = isl_set_universe(dim);
347 isl_int v;
349 isl_int_init(v);
350 isl_int_set_ui(v, val.getZExtValue());
351 aff = isl_aff_add_constant(aff, v);
352 isl_int_clear(v);
354 return isl_pw_aff_alloc(dom, aff);
357 __isl_give isl_pw_aff *PetScan::extract_affine(ImplicitCastExpr *expr)
359 return extract_affine(expr->getSubExpr());
362 static unsigned get_type_size(ValueDecl *decl)
364 return decl->getASTContext().getIntWidth(decl->getType());
367 /* Bound parameter "pos" of "set" to the possible values of "decl".
369 static __isl_give isl_set *set_parameter_bounds(__isl_take isl_set *set,
370 unsigned pos, ValueDecl *decl)
372 unsigned width;
373 isl_int v;
375 isl_int_init(v);
377 width = get_type_size(decl);
378 if (decl->getType()->isUnsignedIntegerType()) {
379 set = isl_set_lower_bound_si(set, isl_dim_param, pos, 0);
380 isl_int_set_si(v, 1);
381 isl_int_mul_2exp(v, v, width);
382 isl_int_sub_ui(v, v, 1);
383 set = isl_set_upper_bound(set, isl_dim_param, pos, v);
384 } else {
385 isl_int_set_si(v, 1);
386 isl_int_mul_2exp(v, v, width - 1);
387 isl_int_sub_ui(v, v, 1);
388 set = isl_set_upper_bound(set, isl_dim_param, pos, v);
389 isl_int_neg(v, v);
390 isl_int_sub_ui(v, v, 1);
391 set = isl_set_lower_bound(set, isl_dim_param, pos, v);
394 isl_int_clear(v);
396 return set;
399 /* Extract an affine expression from the DeclRefExpr "expr".
401 * If the variable has been assigned a value, then we check whether
402 * we know what (affine) value was assigned.
403 * If so, we return this value. Otherwise we convert "expr"
404 * to an extra parameter (provided nesting_enabled is set).
406 * Otherwise, we simply return an expression that is equal
407 * to a parameter corresponding to the referenced variable.
409 __isl_give isl_pw_aff *PetScan::extract_affine(DeclRefExpr *expr)
411 ValueDecl *decl = expr->getDecl();
412 const Type *type = decl->getType().getTypePtr();
413 isl_id *id;
414 isl_space *dim;
415 isl_aff *aff;
416 isl_set *dom;
418 if (!type->isIntegerType()) {
419 unsupported(expr);
420 return NULL;
423 if (assigned_value.find(decl) != assigned_value.end()) {
424 if (assigned_value[decl])
425 return isl_pw_aff_copy(assigned_value[decl]);
426 else
427 return nested_access(expr);
430 id = isl_id_alloc(ctx, decl->getName().str().c_str(), decl);
431 dim = isl_space_params_alloc(ctx, 1);
433 dim = isl_space_set_dim_id(dim, isl_dim_param, 0, id);
435 dom = isl_set_universe(isl_space_copy(dim));
436 aff = isl_aff_zero_on_domain(isl_local_space_from_space(dim));
437 aff = isl_aff_add_coefficient_si(aff, isl_dim_param, 0, 1);
439 return isl_pw_aff_alloc(dom, aff);
442 /* Extract an affine expression from an integer division operation.
443 * In particular, if "expr" is lhs/rhs, then return
445 * lhs >= 0 ? floor(lhs/rhs) : ceil(lhs/rhs)
447 * The second argument (rhs) is required to be a (positive) integer constant.
449 __isl_give isl_pw_aff *PetScan::extract_affine_div(BinaryOperator *expr)
451 Expr *rhs_expr;
452 isl_pw_aff *lhs, *lhs_f, *lhs_c;
453 isl_pw_aff *res;
454 isl_int v;
455 isl_set *cond;
457 rhs_expr = expr->getRHS();
458 isl_int_init(v);
459 if (extract_int(rhs_expr, &v) < 0) {
460 isl_int_clear(v);
461 return NULL;
464 lhs = extract_affine(expr->getLHS());
465 cond = isl_pw_aff_nonneg_set(isl_pw_aff_copy(lhs));
467 lhs = isl_pw_aff_scale_down(lhs, v);
468 isl_int_clear(v);
470 lhs_f = isl_pw_aff_floor(isl_pw_aff_copy(lhs));
471 lhs_c = isl_pw_aff_ceil(lhs);
472 res = isl_pw_aff_cond(isl_set_indicator_function(cond), lhs_f, lhs_c);
474 return res;
477 /* Extract an affine expression from a modulo operation.
478 * In particular, if "expr" is lhs/rhs, then return
480 * lhs - rhs * (lhs >= 0 ? floor(lhs/rhs) : ceil(lhs/rhs))
482 * The second argument (rhs) is required to be a (positive) integer constant.
484 __isl_give isl_pw_aff *PetScan::extract_affine_mod(BinaryOperator *expr)
486 Expr *rhs_expr;
487 isl_pw_aff *lhs, *lhs_f, *lhs_c;
488 isl_pw_aff *res;
489 isl_int v;
490 isl_set *cond;
492 rhs_expr = expr->getRHS();
493 if (rhs_expr->getStmtClass() != Stmt::IntegerLiteralClass) {
494 unsupported(expr);
495 return NULL;
498 lhs = extract_affine(expr->getLHS());
499 cond = isl_pw_aff_nonneg_set(isl_pw_aff_copy(lhs));
501 isl_int_init(v);
502 extract_int(cast<IntegerLiteral>(rhs_expr), &v);
503 res = isl_pw_aff_scale_down(isl_pw_aff_copy(lhs), v);
505 lhs_f = isl_pw_aff_floor(isl_pw_aff_copy(res));
506 lhs_c = isl_pw_aff_ceil(res);
507 res = isl_pw_aff_cond(isl_set_indicator_function(cond), lhs_f, lhs_c);
509 res = isl_pw_aff_scale(res, v);
510 isl_int_clear(v);
512 res = isl_pw_aff_sub(lhs, res);
514 return res;
517 /* Extract an affine expression from a multiplication operation.
518 * This is only allowed if at least one of the two arguments
519 * is a (piecewise) constant.
521 __isl_give isl_pw_aff *PetScan::extract_affine_mul(BinaryOperator *expr)
523 isl_pw_aff *lhs;
524 isl_pw_aff *rhs;
526 lhs = extract_affine(expr->getLHS());
527 rhs = extract_affine(expr->getRHS());
529 if (!isl_pw_aff_is_cst(lhs) && !isl_pw_aff_is_cst(rhs)) {
530 isl_pw_aff_free(lhs);
531 isl_pw_aff_free(rhs);
532 unsupported(expr);
533 return NULL;
536 return isl_pw_aff_mul(lhs, rhs);
539 /* Extract an affine expression from an addition or subtraction operation.
541 __isl_give isl_pw_aff *PetScan::extract_affine_add(BinaryOperator *expr)
543 isl_pw_aff *lhs;
544 isl_pw_aff *rhs;
546 lhs = extract_affine(expr->getLHS());
547 rhs = extract_affine(expr->getRHS());
549 switch (expr->getOpcode()) {
550 case BO_Add:
551 return isl_pw_aff_add(lhs, rhs);
552 case BO_Sub:
553 return isl_pw_aff_sub(lhs, rhs);
554 default:
555 isl_pw_aff_free(lhs);
556 isl_pw_aff_free(rhs);
557 return NULL;
562 /* Compute
564 * pwaff mod 2^width
566 static __isl_give isl_pw_aff *wrap(__isl_take isl_pw_aff *pwaff,
567 unsigned width)
569 isl_int mod;
571 isl_int_init(mod);
572 isl_int_set_si(mod, 1);
573 isl_int_mul_2exp(mod, mod, width);
575 pwaff = isl_pw_aff_mod(pwaff, mod);
577 isl_int_clear(mod);
579 return pwaff;
582 /* Limit the domain of "pwaff" to those elements where the function
583 * value satisfies
585 * 2^{width-1} <= pwaff < 2^{width-1}
587 static __isl_give isl_pw_aff *avoid_overflow(__isl_take isl_pw_aff *pwaff,
588 unsigned width)
590 isl_int v;
591 isl_space *space = isl_pw_aff_get_domain_space(pwaff);
592 isl_local_space *ls = isl_local_space_from_space(space);
593 isl_aff *bound;
594 isl_set *dom;
595 isl_pw_aff *b;
597 isl_int_init(v);
598 isl_int_set_si(v, 1);
599 isl_int_mul_2exp(v, v, width - 1);
601 bound = isl_aff_zero_on_domain(ls);
602 bound = isl_aff_add_constant(bound, v);
603 b = isl_pw_aff_from_aff(bound);
605 dom = isl_pw_aff_lt_set(isl_pw_aff_copy(pwaff), isl_pw_aff_copy(b));
606 pwaff = isl_pw_aff_intersect_domain(pwaff, dom);
608 b = isl_pw_aff_neg(b);
609 dom = isl_pw_aff_ge_set(isl_pw_aff_copy(pwaff), b);
610 pwaff = isl_pw_aff_intersect_domain(pwaff, dom);
612 isl_int_clear(v);
614 return pwaff;
617 /* Return the piecewise affine expression "set ? 1 : 0" defined on "dom".
619 static __isl_give isl_pw_aff *indicator_function(__isl_take isl_set *set,
620 __isl_take isl_set *dom)
622 isl_pw_aff *pa;
623 pa = isl_set_indicator_function(set);
624 pa = isl_pw_aff_intersect_domain(pa, dom);
625 return pa;
628 /* Extract an affine expression from some binary operations.
629 * If the result of the expression is unsigned, then we wrap it
630 * based on the size of the type. Otherwise, we ensure that
631 * no overflow occurs.
633 __isl_give isl_pw_aff *PetScan::extract_affine(BinaryOperator *expr)
635 isl_pw_aff *res;
636 unsigned width;
638 switch (expr->getOpcode()) {
639 case BO_Add:
640 case BO_Sub:
641 res = extract_affine_add(expr);
642 break;
643 case BO_Div:
644 res = extract_affine_div(expr);
645 break;
646 case BO_Rem:
647 res = extract_affine_mod(expr);
648 break;
649 case BO_Mul:
650 res = extract_affine_mul(expr);
651 break;
652 case BO_LT:
653 case BO_LE:
654 case BO_GT:
655 case BO_GE:
656 case BO_EQ:
657 case BO_NE:
658 case BO_LAnd:
659 case BO_LOr:
660 return extract_condition(expr);
661 default:
662 unsupported(expr);
663 return NULL;
666 width = ast_context.getIntWidth(expr->getType());
667 if (expr->getType()->isUnsignedIntegerType())
668 res = wrap(res, width);
669 else
670 res = avoid_overflow(res, width);
672 return res;
675 /* Extract an affine expression from a negation operation.
677 __isl_give isl_pw_aff *PetScan::extract_affine(UnaryOperator *expr)
679 if (expr->getOpcode() == UO_Minus)
680 return isl_pw_aff_neg(extract_affine(expr->getSubExpr()));
681 if (expr->getOpcode() == UO_LNot)
682 return extract_condition(expr);
684 unsupported(expr);
685 return NULL;
688 __isl_give isl_pw_aff *PetScan::extract_affine(ParenExpr *expr)
690 return extract_affine(expr->getSubExpr());
693 /* Extract an affine expression from some special function calls.
694 * In particular, we handle "min", "max", "ceild" and "floord".
695 * In case of the latter two, the second argument needs to be
696 * a (positive) integer constant.
698 __isl_give isl_pw_aff *PetScan::extract_affine(CallExpr *expr)
700 FunctionDecl *fd;
701 string name;
702 isl_pw_aff *aff1, *aff2;
704 fd = expr->getDirectCallee();
705 if (!fd) {
706 unsupported(expr);
707 return NULL;
710 name = fd->getDeclName().getAsString();
711 if (!(expr->getNumArgs() == 2 && name == "min") &&
712 !(expr->getNumArgs() == 2 && name == "max") &&
713 !(expr->getNumArgs() == 2 && name == "floord") &&
714 !(expr->getNumArgs() == 2 && name == "ceild")) {
715 unsupported(expr);
716 return NULL;
719 if (name == "min" || name == "max") {
720 aff1 = extract_affine(expr->getArg(0));
721 aff2 = extract_affine(expr->getArg(1));
723 if (name == "min")
724 aff1 = isl_pw_aff_min(aff1, aff2);
725 else
726 aff1 = isl_pw_aff_max(aff1, aff2);
727 } else if (name == "floord" || name == "ceild") {
728 isl_int v;
729 Expr *arg2 = expr->getArg(1);
731 if (arg2->getStmtClass() != Stmt::IntegerLiteralClass) {
732 unsupported(expr);
733 return NULL;
735 aff1 = extract_affine(expr->getArg(0));
736 isl_int_init(v);
737 extract_int(cast<IntegerLiteral>(arg2), &v);
738 aff1 = isl_pw_aff_scale_down(aff1, v);
739 isl_int_clear(v);
740 if (name == "floord")
741 aff1 = isl_pw_aff_floor(aff1);
742 else
743 aff1 = isl_pw_aff_ceil(aff1);
744 } else {
745 unsupported(expr);
746 return NULL;
749 return aff1;
753 /* This method is called when we come across an access that is
754 * nested in what is supposed to be an affine expression.
755 * If nesting is allowed, we return a new parameter that corresponds
756 * to this nested access. Otherwise, we simply complain.
758 * The new parameter is resolved in resolve_nested.
760 isl_pw_aff *PetScan::nested_access(Expr *expr)
762 isl_id *id;
763 isl_space *dim;
764 isl_aff *aff;
765 isl_set *dom;
767 if (!nesting_enabled) {
768 unsupported(expr);
769 return NULL;
772 id = isl_id_alloc(ctx, NULL, expr);
773 dim = isl_space_params_alloc(ctx, 1);
775 dim = isl_space_set_dim_id(dim, isl_dim_param, 0, id);
777 dom = isl_set_universe(isl_space_copy(dim));
778 aff = isl_aff_zero_on_domain(isl_local_space_from_space(dim));
779 aff = isl_aff_add_coefficient_si(aff, isl_dim_param, 0, 1);
781 return isl_pw_aff_alloc(dom, aff);
784 /* Affine expressions are not supposed to contain array accesses,
785 * but if nesting is allowed, we return a parameter corresponding
786 * to the array access.
788 __isl_give isl_pw_aff *PetScan::extract_affine(ArraySubscriptExpr *expr)
790 return nested_access(expr);
793 /* Extract an affine expression from a conditional operation.
795 __isl_give isl_pw_aff *PetScan::extract_affine(ConditionalOperator *expr)
797 isl_pw_aff *cond, *lhs, *rhs, *res;
799 cond = extract_condition(expr->getCond());
800 lhs = extract_affine(expr->getTrueExpr());
801 rhs = extract_affine(expr->getFalseExpr());
803 return isl_pw_aff_cond(cond, lhs, rhs);
806 /* Extract an affine expression, if possible, from "expr".
807 * Otherwise return NULL.
809 __isl_give isl_pw_aff *PetScan::extract_affine(Expr *expr)
811 switch (expr->getStmtClass()) {
812 case Stmt::ImplicitCastExprClass:
813 return extract_affine(cast<ImplicitCastExpr>(expr));
814 case Stmt::IntegerLiteralClass:
815 return extract_affine(cast<IntegerLiteral>(expr));
816 case Stmt::DeclRefExprClass:
817 return extract_affine(cast<DeclRefExpr>(expr));
818 case Stmt::BinaryOperatorClass:
819 return extract_affine(cast<BinaryOperator>(expr));
820 case Stmt::UnaryOperatorClass:
821 return extract_affine(cast<UnaryOperator>(expr));
822 case Stmt::ParenExprClass:
823 return extract_affine(cast<ParenExpr>(expr));
824 case Stmt::CallExprClass:
825 return extract_affine(cast<CallExpr>(expr));
826 case Stmt::ArraySubscriptExprClass:
827 return extract_affine(cast<ArraySubscriptExpr>(expr));
828 case Stmt::ConditionalOperatorClass:
829 return extract_affine(cast<ConditionalOperator>(expr));
830 default:
831 unsupported(expr);
833 return NULL;
836 __isl_give isl_map *PetScan::extract_access(ImplicitCastExpr *expr)
838 return extract_access(expr->getSubExpr());
841 /* Return the depth of an array of the given type.
843 static int array_depth(const Type *type)
845 if (type->isPointerType())
846 return 1 + array_depth(type->getPointeeType().getTypePtr());
847 if (type->isArrayType()) {
848 const ArrayType *atype;
849 type = type->getCanonicalTypeInternal().getTypePtr();
850 atype = cast<ArrayType>(type);
851 return 1 + array_depth(atype->getElementType().getTypePtr());
853 return 0;
856 /* Return the element type of the given array type.
858 static QualType base_type(QualType qt)
860 const Type *type = qt.getTypePtr();
862 if (type->isPointerType())
863 return base_type(type->getPointeeType());
864 if (type->isArrayType()) {
865 const ArrayType *atype;
866 type = type->getCanonicalTypeInternal().getTypePtr();
867 atype = cast<ArrayType>(type);
868 return base_type(atype->getElementType());
870 return qt;
873 /* Extract an access relation from a reference to a variable.
874 * If the variable has name "A" and its type corresponds to an
875 * array of depth d, then the returned access relation is of the
876 * form
878 * { [] -> A[i_1,...,i_d] }
880 __isl_give isl_map *PetScan::extract_access(DeclRefExpr *expr)
882 ValueDecl *decl = expr->getDecl();
883 int depth = array_depth(decl->getType().getTypePtr());
884 isl_id *id = isl_id_alloc(ctx, decl->getName().str().c_str(), decl);
885 isl_space *dim = isl_space_alloc(ctx, 0, 0, depth);
886 isl_map *access_rel;
888 dim = isl_space_set_tuple_id(dim, isl_dim_out, id);
890 access_rel = isl_map_universe(dim);
892 return access_rel;
895 /* Extract an access relation from an integer contant.
896 * If the value of the constant is "v", then the returned access relation
897 * is
899 * { [] -> [v] }
901 __isl_give isl_map *PetScan::extract_access(IntegerLiteral *expr)
903 return isl_map_from_range(isl_set_from_pw_aff(extract_affine(expr)));
906 /* Try and extract an access relation from the given Expr.
907 * Return NULL if it doesn't work out.
909 __isl_give isl_map *PetScan::extract_access(Expr *expr)
911 switch (expr->getStmtClass()) {
912 case Stmt::ImplicitCastExprClass:
913 return extract_access(cast<ImplicitCastExpr>(expr));
914 case Stmt::DeclRefExprClass:
915 return extract_access(cast<DeclRefExpr>(expr));
916 case Stmt::ArraySubscriptExprClass:
917 return extract_access(cast<ArraySubscriptExpr>(expr));
918 default:
919 unsupported(expr);
921 return NULL;
924 /* Assign the affine expression "index" to the output dimension "pos" of "map",
925 * restrict the domain to those values that result in a non-negative index
926 * and return the result.
928 __isl_give isl_map *set_index(__isl_take isl_map *map, int pos,
929 __isl_take isl_pw_aff *index)
931 isl_map *index_map;
932 int len = isl_map_dim(map, isl_dim_out);
933 isl_id *id;
934 isl_set *domain;
936 domain = isl_pw_aff_nonneg_set(isl_pw_aff_copy(index));
937 index = isl_pw_aff_intersect_domain(index, domain);
938 index_map = isl_map_from_range(isl_set_from_pw_aff(index));
939 index_map = isl_map_insert_dims(index_map, isl_dim_out, 0, pos);
940 index_map = isl_map_add_dims(index_map, isl_dim_out, len - pos - 1);
941 id = isl_map_get_tuple_id(map, isl_dim_out);
942 index_map = isl_map_set_tuple_id(index_map, isl_dim_out, id);
944 map = isl_map_intersect(map, index_map);
946 return map;
949 /* Extract an access relation from the given array subscript expression.
950 * If nesting is allowed in general, then we turn it on while
951 * examining the index expression.
953 * We first extract an access relation from the base.
954 * This will result in an access relation with a range that corresponds
955 * to the array being accessed and with earlier indices filled in already.
956 * We then extract the current index and fill that in as well.
957 * The position of the current index is based on the type of base.
958 * If base is the actual array variable, then the depth of this type
959 * will be the same as the depth of the array and we will fill in
960 * the first array index.
961 * Otherwise, the depth of the base type will be smaller and we will fill
962 * in a later index.
964 __isl_give isl_map *PetScan::extract_access(ArraySubscriptExpr *expr)
966 Expr *base = expr->getBase();
967 Expr *idx = expr->getIdx();
968 isl_pw_aff *index;
969 isl_map *base_access;
970 isl_map *access;
971 int depth = array_depth(base->getType().getTypePtr());
972 int pos;
973 bool save_nesting = nesting_enabled;
975 nesting_enabled = allow_nested;
977 base_access = extract_access(base);
978 index = extract_affine(idx);
980 nesting_enabled = save_nesting;
982 pos = isl_map_dim(base_access, isl_dim_out) - depth;
983 access = set_index(base_access, pos, index);
985 return access;
988 /* Check if "expr" calls function "minmax" with two arguments and if so
989 * make lhs and rhs refer to these two arguments.
991 static bool is_minmax(Expr *expr, const char *minmax, Expr *&lhs, Expr *&rhs)
993 CallExpr *call;
994 FunctionDecl *fd;
995 string name;
997 if (expr->getStmtClass() != Stmt::CallExprClass)
998 return false;
1000 call = cast<CallExpr>(expr);
1001 fd = call->getDirectCallee();
1002 if (!fd)
1003 return false;
1005 if (call->getNumArgs() != 2)
1006 return false;
1008 name = fd->getDeclName().getAsString();
1009 if (name != minmax)
1010 return false;
1012 lhs = call->getArg(0);
1013 rhs = call->getArg(1);
1015 return true;
1018 /* Check if "expr" is of the form min(lhs, rhs) and if so make
1019 * lhs and rhs refer to the two arguments.
1021 static bool is_min(Expr *expr, Expr *&lhs, Expr *&rhs)
1023 return is_minmax(expr, "min", lhs, rhs);
1026 /* Check if "expr" is of the form max(lhs, rhs) and if so make
1027 * lhs and rhs refer to the two arguments.
1029 static bool is_max(Expr *expr, Expr *&lhs, Expr *&rhs)
1031 return is_minmax(expr, "max", lhs, rhs);
1034 /* Return "lhs && rhs", defined on the shared definition domain.
1036 static __isl_give isl_pw_aff *pw_aff_and(__isl_take isl_pw_aff *lhs,
1037 __isl_take isl_pw_aff *rhs)
1039 isl_set *cond;
1040 isl_set *dom;
1042 dom = isl_set_intersect(isl_pw_aff_domain(isl_pw_aff_copy(lhs)),
1043 isl_pw_aff_domain(isl_pw_aff_copy(rhs)));
1044 cond = isl_set_intersect(isl_pw_aff_non_zero_set(lhs),
1045 isl_pw_aff_non_zero_set(rhs));
1046 return indicator_function(cond, dom);
1049 /* Return "lhs && rhs", with shortcut semantics.
1050 * That is, if lhs is false, then the result is defined even if rhs is not.
1051 * In practice, we compute lhs ? rhs : lhs.
1053 static __isl_give isl_pw_aff *pw_aff_and_then(__isl_take isl_pw_aff *lhs,
1054 __isl_take isl_pw_aff *rhs)
1056 return isl_pw_aff_cond(isl_pw_aff_copy(lhs), rhs, lhs);
1059 /* Return "lhs || rhs", with shortcut semantics.
1060 * That is, if lhs is true, then the result is defined even if rhs is not.
1061 * In practice, we compute lhs ? lhs : rhs.
1063 static __isl_give isl_pw_aff *pw_aff_or_else(__isl_take isl_pw_aff *lhs,
1064 __isl_take isl_pw_aff *rhs)
1066 return isl_pw_aff_cond(isl_pw_aff_copy(lhs), lhs, rhs);
1069 /* Extract an affine expressions representing the comparison "LHS op RHS"
1070 * "comp" is the original statement that "LHS op RHS" is derived from
1071 * and is used for diagnostics.
1073 * If the comparison is of the form
1075 * a <= min(b,c)
1077 * then the expression is constructed as the conjunction of
1078 * the comparisons
1080 * a <= b and a <= c
1082 * A similar optimization is performed for max(a,b) <= c.
1083 * We do this because that will lead to simpler representations
1084 * of the expression.
1085 * If isl is ever enhanced to explicitly deal with min and max expressions,
1086 * this optimization can be removed.
1088 __isl_give isl_pw_aff *PetScan::extract_comparison(BinaryOperatorKind op,
1089 Expr *LHS, Expr *RHS, Stmt *comp)
1091 isl_pw_aff *lhs;
1092 isl_pw_aff *rhs;
1093 isl_pw_aff *res;
1094 isl_set *cond;
1095 isl_set *dom;
1097 if (op == BO_GT)
1098 return extract_comparison(BO_LT, RHS, LHS, comp);
1099 if (op == BO_GE)
1100 return extract_comparison(BO_LE, RHS, LHS, comp);
1102 if (op == BO_LT || op == BO_LE) {
1103 Expr *expr1, *expr2;
1104 if (is_min(RHS, expr1, expr2)) {
1105 lhs = extract_comparison(op, LHS, expr1, comp);
1106 rhs = extract_comparison(op, LHS, expr2, comp);
1107 return pw_aff_and(lhs, rhs);
1109 if (is_max(LHS, expr1, expr2)) {
1110 lhs = extract_comparison(op, expr1, RHS, comp);
1111 rhs = extract_comparison(op, expr2, RHS, comp);
1112 return pw_aff_and(lhs, rhs);
1116 lhs = extract_affine(LHS);
1117 rhs = extract_affine(RHS);
1119 dom = isl_pw_aff_domain(isl_pw_aff_copy(lhs));
1120 dom = isl_set_intersect(dom, isl_pw_aff_domain(isl_pw_aff_copy(rhs)));
1122 switch (op) {
1123 case BO_LT:
1124 cond = isl_pw_aff_lt_set(lhs, rhs);
1125 break;
1126 case BO_LE:
1127 cond = isl_pw_aff_le_set(lhs, rhs);
1128 break;
1129 case BO_EQ:
1130 cond = isl_pw_aff_eq_set(lhs, rhs);
1131 break;
1132 case BO_NE:
1133 cond = isl_pw_aff_ne_set(lhs, rhs);
1134 break;
1135 default:
1136 isl_pw_aff_free(lhs);
1137 isl_pw_aff_free(rhs);
1138 isl_set_free(dom);
1139 unsupported(comp);
1140 return NULL;
1143 cond = isl_set_coalesce(cond);
1144 res = indicator_function(cond, dom);
1146 return res;
1149 __isl_give isl_pw_aff *PetScan::extract_comparison(BinaryOperator *comp)
1151 return extract_comparison(comp->getOpcode(), comp->getLHS(),
1152 comp->getRHS(), comp);
1155 /* Extract an affine expression representing the negation (logical not)
1156 * of a subexpression.
1158 __isl_give isl_pw_aff *PetScan::extract_boolean(UnaryOperator *op)
1160 isl_set *set_cond, *dom;
1161 isl_pw_aff *cond, *res;
1163 cond = extract_condition(op->getSubExpr());
1165 dom = isl_pw_aff_domain(isl_pw_aff_copy(cond));
1167 set_cond = isl_pw_aff_zero_set(cond);
1169 res = indicator_function(set_cond, dom);
1171 return res;
1174 /* Extract an affine expression representing the disjunction (logical or)
1175 * or conjunction (logical and) of two subexpressions.
1177 __isl_give isl_pw_aff *PetScan::extract_boolean(BinaryOperator *comp)
1179 isl_pw_aff *lhs, *rhs;
1181 lhs = extract_condition(comp->getLHS());
1182 rhs = extract_condition(comp->getRHS());
1184 switch (comp->getOpcode()) {
1185 case BO_LAnd:
1186 return pw_aff_and_then(lhs, rhs);
1187 case BO_LOr:
1188 return pw_aff_or_else(lhs, rhs);
1189 default:
1190 isl_pw_aff_free(lhs);
1191 isl_pw_aff_free(rhs);
1194 unsupported(comp);
1195 return NULL;
1198 __isl_give isl_pw_aff *PetScan::extract_condition(UnaryOperator *expr)
1200 switch (expr->getOpcode()) {
1201 case UO_LNot:
1202 return extract_boolean(expr);
1203 default:
1204 unsupported(expr);
1205 return NULL;
1209 /* Extract the affine expression "expr != 0 ? 1 : 0".
1211 __isl_give isl_pw_aff *PetScan::extract_implicit_condition(Expr *expr)
1213 isl_pw_aff *res;
1214 isl_set *set, *dom;
1216 res = extract_affine(expr);
1218 dom = isl_pw_aff_domain(isl_pw_aff_copy(res));
1219 set = isl_pw_aff_non_zero_set(res);
1221 res = indicator_function(set, dom);
1223 return res;
1226 /* Extract an affine expression from a boolean expression.
1227 * In particular, return the expression "expr ? 1 : 0".
1229 * If the expression doesn't look like a condition, we assume it
1230 * is an affine expression and return the condition "expr != 0 ? 1 : 0".
1232 __isl_give isl_pw_aff *PetScan::extract_condition(Expr *expr)
1234 BinaryOperator *comp;
1236 if (!expr) {
1237 isl_set *u = isl_set_universe(isl_space_params_alloc(ctx, 0));
1238 return indicator_function(u, isl_set_copy(u));
1241 if (expr->getStmtClass() == Stmt::ParenExprClass)
1242 return extract_condition(cast<ParenExpr>(expr)->getSubExpr());
1244 if (expr->getStmtClass() == Stmt::UnaryOperatorClass)
1245 return extract_condition(cast<UnaryOperator>(expr));
1247 if (expr->getStmtClass() != Stmt::BinaryOperatorClass)
1248 return extract_implicit_condition(expr);
1250 comp = cast<BinaryOperator>(expr);
1251 switch (comp->getOpcode()) {
1252 case BO_LT:
1253 case BO_LE:
1254 case BO_GT:
1255 case BO_GE:
1256 case BO_EQ:
1257 case BO_NE:
1258 return extract_comparison(comp);
1259 case BO_LAnd:
1260 case BO_LOr:
1261 return extract_boolean(comp);
1262 default:
1263 return extract_implicit_condition(expr);
1267 static enum pet_op_type UnaryOperatorKind2pet_op_type(UnaryOperatorKind kind)
1269 switch (kind) {
1270 case UO_Minus:
1271 return pet_op_minus;
1272 default:
1273 return pet_op_last;
1277 static enum pet_op_type BinaryOperatorKind2pet_op_type(BinaryOperatorKind kind)
1279 switch (kind) {
1280 case BO_AddAssign:
1281 return pet_op_add_assign;
1282 case BO_SubAssign:
1283 return pet_op_sub_assign;
1284 case BO_MulAssign:
1285 return pet_op_mul_assign;
1286 case BO_DivAssign:
1287 return pet_op_div_assign;
1288 case BO_Assign:
1289 return pet_op_assign;
1290 case BO_Add:
1291 return pet_op_add;
1292 case BO_Sub:
1293 return pet_op_sub;
1294 case BO_Mul:
1295 return pet_op_mul;
1296 case BO_Div:
1297 return pet_op_div;
1298 case BO_EQ:
1299 return pet_op_eq;
1300 case BO_LE:
1301 return pet_op_le;
1302 case BO_LT:
1303 return pet_op_lt;
1304 case BO_GT:
1305 return pet_op_gt;
1306 default:
1307 return pet_op_last;
1311 /* Construct a pet_expr representing a unary operator expression.
1313 struct pet_expr *PetScan::extract_expr(UnaryOperator *expr)
1315 struct pet_expr *arg;
1316 enum pet_op_type op;
1318 op = UnaryOperatorKind2pet_op_type(expr->getOpcode());
1319 if (op == pet_op_last) {
1320 unsupported(expr);
1321 return NULL;
1324 arg = extract_expr(expr->getSubExpr());
1326 return pet_expr_new_unary(ctx, op, arg);
1329 /* Mark the given access pet_expr as a write.
1330 * If a scalar is being accessed, then mark its value
1331 * as unknown in assigned_value.
1333 void PetScan::mark_write(struct pet_expr *access)
1335 isl_id *id;
1336 ValueDecl *decl;
1338 access->acc.write = 1;
1339 access->acc.read = 0;
1341 if (isl_map_dim(access->acc.access, isl_dim_out) != 0)
1342 return;
1344 id = isl_map_get_tuple_id(access->acc.access, isl_dim_out);
1345 decl = (ValueDecl *) isl_id_get_user(id);
1346 clear_assignment(assigned_value, decl);
1347 isl_id_free(id);
1350 /* Construct a pet_expr representing a binary operator expression.
1352 * If the top level operator is an assignment and the LHS is an access,
1353 * then we mark that access as a write. If the operator is a compound
1354 * assignment, the access is marked as both a read and a write.
1356 * If "expr" assigns something to a scalar variable, then we mark
1357 * the variable as having been assigned. If, furthermore, the expression
1358 * is affine, then keep track of this value in assigned_value
1359 * so that we can plug it in when we later come across the same variable.
1361 struct pet_expr *PetScan::extract_expr(BinaryOperator *expr)
1363 struct pet_expr *lhs, *rhs;
1364 enum pet_op_type op;
1366 op = BinaryOperatorKind2pet_op_type(expr->getOpcode());
1367 if (op == pet_op_last) {
1368 unsupported(expr);
1369 return NULL;
1372 lhs = extract_expr(expr->getLHS());
1373 rhs = extract_expr(expr->getRHS());
1375 if (expr->isAssignmentOp() && lhs && lhs->type == pet_expr_access) {
1376 mark_write(lhs);
1377 if (expr->isCompoundAssignmentOp())
1378 lhs->acc.read = 1;
1381 if (expr->getOpcode() == BO_Assign &&
1382 lhs && lhs->type == pet_expr_access &&
1383 isl_map_dim(lhs->acc.access, isl_dim_out) == 0) {
1384 isl_id *id = isl_map_get_tuple_id(lhs->acc.access, isl_dim_out);
1385 ValueDecl *decl = (ValueDecl *) isl_id_get_user(id);
1386 Expr *rhs = expr->getRHS();
1387 isl_pw_aff *pa = try_extract_affine(rhs);
1388 clear_assignment(assigned_value, decl);
1389 if (pa) {
1390 assigned_value[decl] = pa;
1391 insert_expression(pa);
1393 isl_id_free(id);
1396 return pet_expr_new_binary(ctx, op, lhs, rhs);
1399 /* Construct a pet_expr representing a conditional operation.
1401 * We first try to extract the condition as an affine expression.
1402 * If that fails, we construct a pet_expr tree representing the condition.
1404 struct pet_expr *PetScan::extract_expr(ConditionalOperator *expr)
1406 struct pet_expr *cond, *lhs, *rhs;
1407 isl_pw_aff *pa;
1409 pa = try_extract_affine(expr->getCond());
1410 if (pa) {
1411 isl_set *test = isl_set_from_pw_aff(pa);
1412 cond = pet_expr_from_access(isl_map_from_range(test));
1413 } else
1414 cond = extract_expr(expr->getCond());
1415 lhs = extract_expr(expr->getTrueExpr());
1416 rhs = extract_expr(expr->getFalseExpr());
1418 return pet_expr_new_ternary(ctx, cond, lhs, rhs);
1421 struct pet_expr *PetScan::extract_expr(ImplicitCastExpr *expr)
1423 return extract_expr(expr->getSubExpr());
1426 /* Construct a pet_expr representing a floating point value.
1428 struct pet_expr *PetScan::extract_expr(FloatingLiteral *expr)
1430 return pet_expr_new_double(ctx, expr->getValueAsApproximateDouble());
1433 /* Extract an access relation from "expr" and then convert it into
1434 * a pet_expr.
1436 struct pet_expr *PetScan::extract_access_expr(Expr *expr)
1438 isl_map *access;
1439 struct pet_expr *pe;
1441 switch (expr->getStmtClass()) {
1442 case Stmt::ArraySubscriptExprClass:
1443 access = extract_access(cast<ArraySubscriptExpr>(expr));
1444 break;
1445 case Stmt::DeclRefExprClass:
1446 access = extract_access(cast<DeclRefExpr>(expr));
1447 break;
1448 case Stmt::IntegerLiteralClass:
1449 access = extract_access(cast<IntegerLiteral>(expr));
1450 break;
1451 default:
1452 unsupported(expr);
1453 return NULL;
1456 pe = pet_expr_from_access(access);
1458 return pe;
1461 struct pet_expr *PetScan::extract_expr(ParenExpr *expr)
1463 return extract_expr(expr->getSubExpr());
1466 /* Construct a pet_expr representing a function call.
1468 * If we are passing along a pointer to an array element
1469 * or an entire row or even higher dimensional slice of an array,
1470 * then the function being called may write into the array.
1472 * We assume here that if the function is declared to take a pointer
1473 * to a const type, then the function will perform a read
1474 * and that otherwise, it will perform a write.
1476 struct pet_expr *PetScan::extract_expr(CallExpr *expr)
1478 struct pet_expr *res = NULL;
1479 FunctionDecl *fd;
1480 string name;
1482 fd = expr->getDirectCallee();
1483 if (!fd) {
1484 unsupported(expr);
1485 return NULL;
1488 name = fd->getDeclName().getAsString();
1489 res = pet_expr_new_call(ctx, name.c_str(), expr->getNumArgs());
1490 if (!res)
1491 return NULL;
1493 for (int i = 0; i < expr->getNumArgs(); ++i) {
1494 Expr *arg = expr->getArg(i);
1495 int is_addr = 0;
1496 pet_expr *main_arg;
1498 if (arg->getStmtClass() == Stmt::ImplicitCastExprClass) {
1499 ImplicitCastExpr *ice = cast<ImplicitCastExpr>(arg);
1500 arg = ice->getSubExpr();
1502 if (arg->getStmtClass() == Stmt::UnaryOperatorClass) {
1503 UnaryOperator *op = cast<UnaryOperator>(arg);
1504 if (op->getOpcode() == UO_AddrOf) {
1505 is_addr = 1;
1506 arg = op->getSubExpr();
1509 res->args[i] = PetScan::extract_expr(arg);
1510 main_arg = res->args[i];
1511 if (is_addr)
1512 res->args[i] = pet_expr_new_unary(ctx,
1513 pet_op_address_of, res->args[i]);
1514 if (!res->args[i])
1515 goto error;
1516 if (arg->getStmtClass() == Stmt::ArraySubscriptExprClass &&
1517 array_depth(arg->getType().getTypePtr()) > 0)
1518 is_addr = 1;
1519 if (is_addr && main_arg->type == pet_expr_access) {
1520 ParmVarDecl *parm;
1521 if (!fd->hasPrototype()) {
1522 unsupported(expr, "prototype required");
1523 goto error;
1525 parm = fd->getParamDecl(i);
1526 if (!const_base(parm->getType()))
1527 mark_write(main_arg);
1531 return res;
1532 error:
1533 pet_expr_free(res);
1534 return NULL;
1537 /* Try and onstruct a pet_expr representing "expr".
1539 struct pet_expr *PetScan::extract_expr(Expr *expr)
1541 switch (expr->getStmtClass()) {
1542 case Stmt::UnaryOperatorClass:
1543 return extract_expr(cast<UnaryOperator>(expr));
1544 case Stmt::CompoundAssignOperatorClass:
1545 case Stmt::BinaryOperatorClass:
1546 return extract_expr(cast<BinaryOperator>(expr));
1547 case Stmt::ImplicitCastExprClass:
1548 return extract_expr(cast<ImplicitCastExpr>(expr));
1549 case Stmt::ArraySubscriptExprClass:
1550 case Stmt::DeclRefExprClass:
1551 case Stmt::IntegerLiteralClass:
1552 return extract_access_expr(expr);
1553 case Stmt::FloatingLiteralClass:
1554 return extract_expr(cast<FloatingLiteral>(expr));
1555 case Stmt::ParenExprClass:
1556 return extract_expr(cast<ParenExpr>(expr));
1557 case Stmt::ConditionalOperatorClass:
1558 return extract_expr(cast<ConditionalOperator>(expr));
1559 case Stmt::CallExprClass:
1560 return extract_expr(cast<CallExpr>(expr));
1561 default:
1562 unsupported(expr);
1564 return NULL;
1567 /* Check if the given initialization statement is an assignment.
1568 * If so, return that assignment. Otherwise return NULL.
1570 BinaryOperator *PetScan::initialization_assignment(Stmt *init)
1572 BinaryOperator *ass;
1574 if (init->getStmtClass() != Stmt::BinaryOperatorClass)
1575 return NULL;
1577 ass = cast<BinaryOperator>(init);
1578 if (ass->getOpcode() != BO_Assign)
1579 return NULL;
1581 return ass;
1584 /* Check if the given initialization statement is a declaration
1585 * of a single variable.
1586 * If so, return that declaration. Otherwise return NULL.
1588 Decl *PetScan::initialization_declaration(Stmt *init)
1590 DeclStmt *decl;
1592 if (init->getStmtClass() != Stmt::DeclStmtClass)
1593 return NULL;
1595 decl = cast<DeclStmt>(init);
1597 if (!decl->isSingleDecl())
1598 return NULL;
1600 return decl->getSingleDecl();
1603 /* Given the assignment operator in the initialization of a for loop,
1604 * extract the induction variable, i.e., the (integer)variable being
1605 * assigned.
1607 ValueDecl *PetScan::extract_induction_variable(BinaryOperator *init)
1609 Expr *lhs;
1610 DeclRefExpr *ref;
1611 ValueDecl *decl;
1612 const Type *type;
1614 lhs = init->getLHS();
1615 if (lhs->getStmtClass() != Stmt::DeclRefExprClass) {
1616 unsupported(init);
1617 return NULL;
1620 ref = cast<DeclRefExpr>(lhs);
1621 decl = ref->getDecl();
1622 type = decl->getType().getTypePtr();
1624 if (!type->isIntegerType()) {
1625 unsupported(lhs);
1626 return NULL;
1629 return decl;
1632 /* Given the initialization statement of a for loop and the single
1633 * declaration in this initialization statement,
1634 * extract the induction variable, i.e., the (integer) variable being
1635 * declared.
1637 VarDecl *PetScan::extract_induction_variable(Stmt *init, Decl *decl)
1639 VarDecl *vd;
1641 vd = cast<VarDecl>(decl);
1643 const QualType type = vd->getType();
1644 if (!type->isIntegerType()) {
1645 unsupported(init);
1646 return NULL;
1649 if (!vd->getInit()) {
1650 unsupported(init);
1651 return NULL;
1654 return vd;
1657 /* Check that op is of the form iv++ or iv--.
1658 * Return an affine expression "1" or "-1" accordingly.
1660 __isl_give isl_pw_aff *PetScan::extract_unary_increment(
1661 clang::UnaryOperator *op, clang::ValueDecl *iv)
1663 Expr *sub;
1664 DeclRefExpr *ref;
1665 isl_space *space;
1666 isl_aff *aff;
1668 if (!op->isIncrementDecrementOp()) {
1669 unsupported(op);
1670 return NULL;
1673 sub = op->getSubExpr();
1674 if (sub->getStmtClass() != Stmt::DeclRefExprClass) {
1675 unsupported(op);
1676 return NULL;
1679 ref = cast<DeclRefExpr>(sub);
1680 if (ref->getDecl() != iv) {
1681 unsupported(op);
1682 return NULL;
1685 space = isl_space_params_alloc(ctx, 0);
1686 aff = isl_aff_zero_on_domain(isl_local_space_from_space(space));
1688 if (op->isIncrementOp())
1689 aff = isl_aff_add_constant_si(aff, 1);
1690 else
1691 aff = isl_aff_add_constant_si(aff, -1);
1693 return isl_pw_aff_from_aff(aff);
1696 /* If the isl_pw_aff on which isl_pw_aff_foreach_piece is called
1697 * has a single constant expression, then put this constant in *user.
1698 * The caller is assumed to have checked that this function will
1699 * be called exactly once.
1701 static int extract_cst(__isl_take isl_set *set, __isl_take isl_aff *aff,
1702 void *user)
1704 isl_int *inc = (isl_int *)user;
1705 int res = 0;
1707 if (isl_aff_is_cst(aff))
1708 isl_aff_get_constant(aff, inc);
1709 else
1710 res = -1;
1712 isl_set_free(set);
1713 isl_aff_free(aff);
1715 return res;
1718 /* Check if op is of the form
1720 * iv = iv + inc
1722 * and return inc as an affine expression.
1724 * We extract an affine expression from the RHS, subtract iv and return
1725 * the result.
1727 __isl_give isl_pw_aff *PetScan::extract_binary_increment(BinaryOperator *op,
1728 clang::ValueDecl *iv)
1730 Expr *lhs;
1731 DeclRefExpr *ref;
1732 isl_id *id;
1733 isl_space *dim;
1734 isl_aff *aff;
1735 isl_pw_aff *val;
1737 if (op->getOpcode() != BO_Assign) {
1738 unsupported(op);
1739 return NULL;
1742 lhs = op->getLHS();
1743 if (lhs->getStmtClass() != Stmt::DeclRefExprClass) {
1744 unsupported(op);
1745 return NULL;
1748 ref = cast<DeclRefExpr>(lhs);
1749 if (ref->getDecl() != iv) {
1750 unsupported(op);
1751 return NULL;
1754 val = extract_affine(op->getRHS());
1756 id = isl_id_alloc(ctx, iv->getName().str().c_str(), iv);
1758 dim = isl_space_params_alloc(ctx, 1);
1759 dim = isl_space_set_dim_id(dim, isl_dim_param, 0, id);
1760 aff = isl_aff_zero_on_domain(isl_local_space_from_space(dim));
1761 aff = isl_aff_add_coefficient_si(aff, isl_dim_param, 0, 1);
1763 val = isl_pw_aff_sub(val, isl_pw_aff_from_aff(aff));
1765 return val;
1768 /* Check that op is of the form iv += cst or iv -= cst
1769 * and return an affine expression corresponding oto cst or -cst accordingly.
1771 __isl_give isl_pw_aff *PetScan::extract_compound_increment(
1772 CompoundAssignOperator *op, clang::ValueDecl *iv)
1774 Expr *lhs;
1775 DeclRefExpr *ref;
1776 bool neg = false;
1777 isl_pw_aff *val;
1778 BinaryOperatorKind opcode;
1780 opcode = op->getOpcode();
1781 if (opcode != BO_AddAssign && opcode != BO_SubAssign) {
1782 unsupported(op);
1783 return NULL;
1785 if (opcode == BO_SubAssign)
1786 neg = true;
1788 lhs = op->getLHS();
1789 if (lhs->getStmtClass() != Stmt::DeclRefExprClass) {
1790 unsupported(op);
1791 return NULL;
1794 ref = cast<DeclRefExpr>(lhs);
1795 if (ref->getDecl() != iv) {
1796 unsupported(op);
1797 return NULL;
1800 val = extract_affine(op->getRHS());
1801 if (neg)
1802 val = isl_pw_aff_neg(val);
1804 return val;
1807 /* Check that the increment of the given for loop increments
1808 * (or decrements) the induction variable "iv" and return
1809 * the increment as an affine expression if successful.
1811 __isl_give isl_pw_aff *PetScan::extract_increment(clang::ForStmt *stmt,
1812 ValueDecl *iv)
1814 Stmt *inc = stmt->getInc();
1816 if (!inc) {
1817 unsupported(stmt);
1818 return NULL;
1821 if (inc->getStmtClass() == Stmt::UnaryOperatorClass)
1822 return extract_unary_increment(cast<UnaryOperator>(inc), iv);
1823 if (inc->getStmtClass() == Stmt::CompoundAssignOperatorClass)
1824 return extract_compound_increment(
1825 cast<CompoundAssignOperator>(inc), iv);
1826 if (inc->getStmtClass() == Stmt::BinaryOperatorClass)
1827 return extract_binary_increment(cast<BinaryOperator>(inc), iv);
1829 unsupported(inc);
1830 return NULL;
1833 /* Embed the given iteration domain in an extra outer loop
1834 * with induction variable "var".
1835 * If this variable appeared as a parameter in the constraints,
1836 * it is replaced by the new outermost dimension.
1838 static __isl_give isl_set *embed(__isl_take isl_set *set,
1839 __isl_take isl_id *var)
1841 int pos;
1843 set = isl_set_insert_dims(set, isl_dim_set, 0, 1);
1844 pos = isl_set_find_dim_by_id(set, isl_dim_param, var);
1845 if (pos >= 0) {
1846 set = isl_set_equate(set, isl_dim_param, pos, isl_dim_set, 0);
1847 set = isl_set_project_out(set, isl_dim_param, pos, 1);
1850 isl_id_free(var);
1851 return set;
1854 /* Construct a pet_scop for an infinite loop around the given body.
1856 * We extract a pet_scop for the body and then embed it in a loop with
1857 * iteration domain
1859 * { [t] : t >= 0 }
1861 * and schedule
1863 * { [t] -> [t] }
1865 struct pet_scop *PetScan::extract_infinite_loop(Stmt *body)
1867 isl_id *id;
1868 isl_space *dim;
1869 isl_set *domain;
1870 isl_map *sched;
1871 struct pet_scop *scop;
1873 scop = extract(body);
1874 if (!scop)
1875 return NULL;
1877 id = isl_id_alloc(ctx, "t", NULL);
1878 domain = isl_set_nat_universe(isl_space_set_alloc(ctx, 0, 1));
1879 domain = isl_set_set_dim_id(domain, isl_dim_set, 0, isl_id_copy(id));
1880 dim = isl_space_from_domain(isl_set_get_space(domain));
1881 dim = isl_space_add_dims(dim, isl_dim_out, 1);
1882 sched = isl_map_universe(dim);
1883 sched = isl_map_equate(sched, isl_dim_in, 0, isl_dim_out, 0);
1884 scop = pet_scop_embed(scop, domain, sched, id);
1886 return scop;
1889 /* Construct a pet_scop for an infinite loop, i.e., a loop of the form
1891 * for (;;)
1892 * body
1895 struct pet_scop *PetScan::extract_infinite_for(ForStmt *stmt)
1897 return extract_infinite_loop(stmt->getBody());
1900 /* Check if the while loop is of the form
1902 * while (affine expression)
1903 * body
1905 * If so, construct a scop for an infinite loop around body and intersect
1906 * the domain with the affine expression, which may result in an empty loop.
1907 * Otherwise, fail.
1909 struct pet_scop *PetScan::extract(WhileStmt *stmt)
1911 Expr *cond;
1912 isl_pw_aff *pa;
1914 cond = stmt->getCond();
1915 if (!cond) {
1916 unsupported(stmt);
1917 return NULL;
1920 pa = try_extract_affine_condition(cond);
1921 if (pa) {
1922 struct pet_scop *scop;
1923 isl_set *dom;
1924 isl_set *valid;
1926 valid = isl_pw_aff_domain(isl_pw_aff_copy(pa));
1927 dom = isl_pw_aff_non_zero_set(pa);
1928 scop = extract_infinite_loop(stmt->getBody());
1929 scop = pet_scop_restrict(scop, dom);
1930 scop = pet_scop_restrict_context(scop, valid);
1932 return scop;
1935 unsupported(stmt);
1936 return NULL;
1940 /* Check whether "cond" expresses a simple loop bound
1941 * on the only set dimension.
1942 * In particular, if "up" is set then "cond" should contain only
1943 * upper bounds on the set dimension.
1944 * Otherwise, it should contain only lower bounds.
1946 static bool is_simple_bound(__isl_keep isl_set *cond, isl_int inc)
1948 if (isl_int_is_pos(inc))
1949 return !isl_set_dim_has_lower_bound(cond, isl_dim_set, 0);
1950 else
1951 return !isl_set_dim_has_upper_bound(cond, isl_dim_set, 0);
1954 /* Extend a condition on a given iteration of a loop to one that
1955 * imposes the same condition on all previous iterations.
1956 * "domain" expresses the lower [upper] bound on the iterations
1957 * when inc is positive [negative].
1959 * In particular, we construct the condition (when inc is positive)
1961 * forall i' : (domain(i') and i' <= i) => cond(i')
1963 * which is equivalent to
1965 * not exists i' : domain(i') and i' <= i and not cond(i')
1967 * We construct this set by negating cond, applying a map
1969 * { [i'] -> [i] : domain(i') and i' <= i }
1971 * and then negating the result again.
1973 static __isl_give isl_set *valid_for_each_iteration(__isl_take isl_set *cond,
1974 __isl_take isl_set *domain, isl_int inc)
1976 isl_map *previous_to_this;
1978 if (isl_int_is_pos(inc))
1979 previous_to_this = isl_map_lex_le(isl_set_get_space(domain));
1980 else
1981 previous_to_this = isl_map_lex_ge(isl_set_get_space(domain));
1983 previous_to_this = isl_map_intersect_domain(previous_to_this, domain);
1985 cond = isl_set_complement(cond);
1986 cond = isl_set_apply(cond, previous_to_this);
1987 cond = isl_set_complement(cond);
1989 return cond;
1992 /* Construct a domain of the form
1994 * [id] -> { : exists a: id = init + a * inc and a >= 0 }
1996 static __isl_give isl_set *strided_domain(__isl_take isl_id *id,
1997 __isl_take isl_pw_aff *init, isl_int inc)
1999 isl_aff *aff;
2000 isl_space *dim;
2001 isl_set *set;
2003 init = isl_pw_aff_insert_dims(init, isl_dim_in, 0, 1);
2004 dim = isl_pw_aff_get_domain_space(init);
2005 aff = isl_aff_zero_on_domain(isl_local_space_from_space(dim));
2006 aff = isl_aff_add_coefficient(aff, isl_dim_in, 0, inc);
2007 init = isl_pw_aff_add(init, isl_pw_aff_from_aff(aff));
2009 dim = isl_space_set_alloc(isl_pw_aff_get_ctx(init), 1, 1);
2010 dim = isl_space_set_dim_id(dim, isl_dim_param, 0, id);
2011 aff = isl_aff_zero_on_domain(isl_local_space_from_space(dim));
2012 aff = isl_aff_add_coefficient_si(aff, isl_dim_param, 0, 1);
2014 set = isl_pw_aff_eq_set(isl_pw_aff_from_aff(aff), init);
2016 set = isl_set_lower_bound_si(set, isl_dim_set, 0, 0);
2018 return isl_set_params(set);
2021 /* Assuming "cond" represents a bound on a loop where the loop
2022 * iterator "iv" is incremented (or decremented) by one, check if wrapping
2023 * is possible.
2025 * Under the given assumptions, wrapping is only possible if "cond" allows
2026 * for the last value before wrapping, i.e., 2^width - 1 in case of an
2027 * increasing iterator and 0 in case of a decreasing iterator.
2029 static bool can_wrap(__isl_keep isl_set *cond, ValueDecl *iv, isl_int inc)
2031 bool cw;
2032 isl_int limit;
2033 isl_set *test;
2035 test = isl_set_copy(cond);
2037 isl_int_init(limit);
2038 if (isl_int_is_neg(inc))
2039 isl_int_set_si(limit, 0);
2040 else {
2041 isl_int_set_si(limit, 1);
2042 isl_int_mul_2exp(limit, limit, get_type_size(iv));
2043 isl_int_sub_ui(limit, limit, 1);
2046 test = isl_set_fix(cond, isl_dim_set, 0, limit);
2047 cw = !isl_set_is_empty(test);
2048 isl_set_free(test);
2050 isl_int_clear(limit);
2052 return cw;
2055 /* Given a one-dimensional space, construct the following mapping on this
2056 * space
2058 * { [v] -> [v mod 2^width] }
2060 * where width is the number of bits used to represent the values
2061 * of the unsigned variable "iv".
2063 static __isl_give isl_map *compute_wrapping(__isl_take isl_space *dim,
2064 ValueDecl *iv)
2066 isl_int mod;
2067 isl_aff *aff;
2068 isl_map *map;
2070 isl_int_init(mod);
2071 isl_int_set_si(mod, 1);
2072 isl_int_mul_2exp(mod, mod, get_type_size(iv));
2074 aff = isl_aff_zero_on_domain(isl_local_space_from_space(dim));
2075 aff = isl_aff_add_coefficient_si(aff, isl_dim_in, 0, 1);
2076 aff = isl_aff_mod(aff, mod);
2078 isl_int_clear(mod);
2080 return isl_map_from_basic_map(isl_basic_map_from_aff(aff));
2081 map = isl_map_reverse(map);
2084 /* Project out the parameter "id" from "set".
2086 static __isl_give isl_set *set_project_out_by_id(__isl_take isl_set *set,
2087 __isl_keep isl_id *id)
2089 int pos;
2091 pos = isl_set_find_dim_by_id(set, isl_dim_param, id);
2092 if (pos >= 0)
2093 set = isl_set_project_out(set, isl_dim_param, pos, 1);
2095 return set;
2098 /* Compute the set of parameters for which "set1" is a subset of "set2".
2100 * set1 is a subset of set2 if
2102 * forall i in set1 : i in set2
2104 * or
2106 * not exists i in set1 and i not in set2
2108 * i.e.,
2110 * not exists i in set1 \ set2
2112 static __isl_give isl_set *enforce_subset(__isl_take isl_set *set1,
2113 __isl_take isl_set *set2)
2115 return isl_set_complement(isl_set_params(isl_set_subtract(set1, set2)));
2118 /* Compute the set of parameter values for which "cond" holds
2119 * on the next iteration for each element of "dom".
2121 * We first construct mapping { [i] -> [i + inc] }, apply that to "dom"
2122 * and then compute the set of parameters for which the result is a subset
2123 * of "cond".
2125 static __isl_give isl_set *valid_on_next(__isl_take isl_set *cond,
2126 __isl_take isl_set *dom, isl_int inc)
2128 isl_space *space;
2129 isl_aff *aff;
2130 isl_map *next;
2132 space = isl_set_get_space(dom);
2133 aff = isl_aff_zero_on_domain(isl_local_space_from_space(space));
2134 aff = isl_aff_add_coefficient_si(aff, isl_dim_in, 0, 1);
2135 aff = isl_aff_add_constant(aff, inc);
2136 next = isl_map_from_basic_map(isl_basic_map_from_aff(aff));
2138 dom = isl_set_apply(dom, next);
2140 return enforce_subset(dom, cond);
2143 /* Construct a pet_scop for a for statement.
2144 * The for loop is required to be of the form
2146 * for (i = init; condition; ++i)
2148 * or
2150 * for (i = init; condition; --i)
2152 * The initialization of the for loop should either be an assignment
2153 * to an integer variable, or a declaration of such a variable with
2154 * initialization.
2156 * The condition is allowed to contain nested accesses, provided
2157 * they are not being written to inside the body of the loop.
2159 * We extract a pet_scop for the body and then embed it in a loop with
2160 * iteration domain and schedule
2162 * { [i] : i >= init and condition' }
2163 * { [i] -> [i] }
2165 * or
2167 * { [i] : i <= init and condition' }
2168 * { [i] -> [-i] }
2170 * Where condition' is equal to condition if the latter is
2171 * a simple upper [lower] bound and a condition that is extended
2172 * to apply to all previous iterations otherwise.
2174 * If the stride of the loop is not 1, then "i >= init" is replaced by
2176 * (exists a: i = init + stride * a and a >= 0)
2178 * If the loop iterator i is unsigned, then wrapping may occur.
2179 * During the computation, we work with a virtual iterator that
2180 * does not wrap. However, the condition in the code applies
2181 * to the wrapped value, so we need to change condition(i)
2182 * into condition([i % 2^width]).
2183 * After computing the virtual domain and schedule, we apply
2184 * the function { [v] -> [v % 2^width] } to the domain and the domain
2185 * of the schedule. In order not to lose any information, we also
2186 * need to intersect the domain of the schedule with the virtual domain
2187 * first, since some iterations in the wrapped domain may be scheduled
2188 * several times, typically an infinite number of times.
2189 * Note that there is no need to perform this final wrapping
2190 * if the loop condition (after wrapping) is simple.
2192 * Wrapping on unsigned iterators can be avoided entirely if
2193 * loop condition is simple, the loop iterator is incremented
2194 * [decremented] by one and the last value before wrapping cannot
2195 * possibly satisfy the loop condition.
2197 * Before extracting a pet_scop from the body we remove all
2198 * assignments in assigned_value to variables that are assigned
2199 * somewhere in the body of the loop.
2201 * Valid parameters for a for loop are those for which the initial
2202 * value itself, the increment on each domain iteration and
2203 * the condition on both the initial value and
2204 * the result of incrementing the iterator for each iteration of the domain
2205 * can be evaluated.
2207 struct pet_scop *PetScan::extract_for(ForStmt *stmt)
2209 BinaryOperator *ass;
2210 Decl *decl;
2211 Stmt *init;
2212 Expr *lhs, *rhs;
2213 ValueDecl *iv;
2214 isl_space *dim;
2215 isl_set *domain;
2216 isl_map *sched;
2217 isl_set *cond = NULL;
2218 isl_id *id;
2219 struct pet_scop *scop;
2220 assigned_value_cache cache(assigned_value);
2221 isl_int inc;
2222 bool is_one;
2223 bool is_unsigned;
2224 bool is_simple;
2225 bool is_virtual;
2226 isl_map *wrap = NULL;
2227 isl_pw_aff *pa, *pa_inc, *init_val;
2228 isl_set *valid_init;
2229 isl_set *valid_cond;
2230 isl_set *valid_cond_init;
2231 isl_set *valid_cond_next;
2232 isl_set *valid_inc;
2234 if (!stmt->getInit() && !stmt->getCond() && !stmt->getInc())
2235 return extract_infinite_for(stmt);
2237 init = stmt->getInit();
2238 if (!init) {
2239 unsupported(stmt);
2240 return NULL;
2242 if ((ass = initialization_assignment(init)) != NULL) {
2243 iv = extract_induction_variable(ass);
2244 if (!iv)
2245 return NULL;
2246 lhs = ass->getLHS();
2247 rhs = ass->getRHS();
2248 } else if ((decl = initialization_declaration(init)) != NULL) {
2249 VarDecl *var = extract_induction_variable(init, decl);
2250 if (!var)
2251 return NULL;
2252 iv = var;
2253 rhs = var->getInit();
2254 lhs = create_DeclRefExpr(var);
2255 } else {
2256 unsupported(stmt->getInit());
2257 return NULL;
2260 pa_inc = extract_increment(stmt, iv);
2261 if (!pa_inc)
2262 return NULL;
2264 isl_int_init(inc);
2265 if (isl_pw_aff_n_piece(pa_inc) != 1 ||
2266 isl_pw_aff_foreach_piece(pa_inc, &extract_cst, &inc) < 0) {
2267 isl_pw_aff_free(pa_inc);
2268 unsupported(stmt->getInc());
2269 isl_int_clear(inc);
2270 return NULL;
2272 valid_inc = isl_pw_aff_domain(pa_inc);
2274 is_unsigned = iv->getType()->isUnsignedIntegerType();
2276 assigned_value.erase(iv);
2277 clear_assignments clear(assigned_value);
2278 clear.TraverseStmt(stmt->getBody());
2280 id = isl_id_alloc(ctx, iv->getName().str().c_str(), iv);
2282 scop = extract(stmt->getBody());
2284 pa = try_extract_nested_condition(stmt->getCond());
2285 if (pa && !is_nested_allowed(pa, scop)) {
2286 isl_pw_aff_free(pa);
2287 pa = NULL;
2290 if (!pa)
2291 pa = extract_condition(stmt->getCond());
2292 valid_cond = isl_pw_aff_domain(isl_pw_aff_copy(pa));
2293 cond = isl_pw_aff_non_zero_set(pa);
2294 cond = embed(cond, isl_id_copy(id));
2295 valid_cond = isl_set_coalesce(valid_cond);
2296 valid_cond = embed(valid_cond, isl_id_copy(id));
2297 valid_inc = embed(valid_inc, isl_id_copy(id));
2298 is_one = isl_int_is_one(inc) || isl_int_is_negone(inc);
2299 is_virtual = is_unsigned && (!is_one || can_wrap(cond, iv, inc));
2301 init_val = extract_affine(rhs);
2302 valid_cond_init = enforce_subset(
2303 isl_set_from_pw_aff(isl_pw_aff_copy(init_val)),
2304 isl_set_copy(valid_cond));
2305 if (is_one && !is_virtual) {
2306 isl_pw_aff_free(init_val);
2307 pa = extract_comparison(isl_int_is_pos(inc) ? BO_GE : BO_LE,
2308 lhs, rhs, init);
2309 valid_init = isl_pw_aff_domain(isl_pw_aff_copy(pa));
2310 valid_init = set_project_out_by_id(valid_init, id);
2311 domain = isl_pw_aff_non_zero_set(pa);
2312 } else {
2313 valid_init = isl_pw_aff_domain(isl_pw_aff_copy(init_val));
2314 domain = strided_domain(isl_id_copy(id), init_val, inc);
2317 domain = embed(domain, isl_id_copy(id));
2318 if (is_virtual) {
2319 isl_map *rev_wrap;
2320 wrap = compute_wrapping(isl_set_get_space(cond), iv);
2321 rev_wrap = isl_map_reverse(isl_map_copy(wrap));
2322 cond = isl_set_apply(cond, isl_map_copy(rev_wrap));
2323 valid_cond = isl_set_apply(valid_cond, isl_map_copy(rev_wrap));
2324 valid_inc = isl_set_apply(valid_inc, rev_wrap);
2326 cond = isl_set_gist(cond, isl_set_copy(domain));
2327 is_simple = is_simple_bound(cond, inc);
2328 if (!is_simple)
2329 cond = valid_for_each_iteration(cond,
2330 isl_set_copy(domain), inc);
2331 domain = isl_set_intersect(domain, cond);
2332 domain = isl_set_set_dim_id(domain, isl_dim_set, 0, isl_id_copy(id));
2333 dim = isl_space_from_domain(isl_set_get_space(domain));
2334 dim = isl_space_add_dims(dim, isl_dim_out, 1);
2335 sched = isl_map_universe(dim);
2336 if (isl_int_is_pos(inc))
2337 sched = isl_map_equate(sched, isl_dim_in, 0, isl_dim_out, 0);
2338 else
2339 sched = isl_map_oppose(sched, isl_dim_in, 0, isl_dim_out, 0);
2341 valid_cond_next = valid_on_next(valid_cond, isl_set_copy(domain), inc);
2342 valid_inc = enforce_subset(isl_set_copy(domain), valid_inc);
2344 if (is_virtual && !is_simple) {
2345 wrap = isl_map_set_dim_id(wrap,
2346 isl_dim_out, 0, isl_id_copy(id));
2347 sched = isl_map_intersect_domain(sched, isl_set_copy(domain));
2348 domain = isl_set_apply(domain, isl_map_copy(wrap));
2349 sched = isl_map_apply_domain(sched, wrap);
2350 } else
2351 isl_map_free(wrap);
2353 scop = pet_scop_embed(scop, domain, sched, id);
2354 scop = resolve_nested(scop);
2355 clear_assignment(assigned_value, iv);
2357 isl_int_clear(inc);
2359 scop = pet_scop_restrict_context(scop, valid_init);
2360 scop = pet_scop_restrict_context(scop, valid_inc);
2361 scop = pet_scop_restrict_context(scop, valid_cond_next);
2362 scop = pet_scop_restrict_context(scop, valid_cond_init);
2364 return scop;
2367 struct pet_scop *PetScan::extract(CompoundStmt *stmt)
2369 return extract(stmt->children());
2372 /* Does "id" refer to a nested access?
2374 static bool is_nested_parameter(__isl_keep isl_id *id)
2376 return id && isl_id_get_user(id) && !isl_id_get_name(id);
2379 /* Does parameter "pos" of "space" refer to a nested access?
2381 static bool is_nested_parameter(__isl_keep isl_space *space, int pos)
2383 bool nested;
2384 isl_id *id;
2386 id = isl_space_get_dim_id(space, isl_dim_param, pos);
2387 nested = is_nested_parameter(id);
2388 isl_id_free(id);
2390 return nested;
2393 /* Does parameter "pos" of "map" refer to a nested access?
2395 static bool is_nested_parameter(__isl_keep isl_map *map, int pos)
2397 bool nested;
2398 isl_id *id;
2400 id = isl_map_get_dim_id(map, isl_dim_param, pos);
2401 nested = is_nested_parameter(id);
2402 isl_id_free(id);
2404 return nested;
2407 /* How many parameters of "space" refer to nested accesses, i.e., have no name?
2409 static int n_nested_parameter(__isl_keep isl_space *space)
2411 int n = 0;
2412 int nparam;
2414 nparam = isl_space_dim(space, isl_dim_param);
2415 for (int i = 0; i < nparam; ++i)
2416 if (is_nested_parameter(space, i))
2417 ++n;
2419 return n;
2422 /* How many parameters of "map" refer to nested accesses, i.e., have no name?
2424 static int n_nested_parameter(__isl_keep isl_map *map)
2426 isl_space *space;
2427 int n;
2429 space = isl_map_get_space(map);
2430 n = n_nested_parameter(space);
2431 isl_space_free(space);
2433 return n;
2436 /* For each nested access parameter in "space",
2437 * construct a corresponding pet_expr, place it in args and
2438 * record its position in "param2pos".
2439 * "n_arg" is the number of elements that are already in args.
2440 * The position recorded in "param2pos" takes this number into account.
2441 * If the pet_expr corresponding to a parameter is identical to
2442 * the pet_expr corresponding to an earlier parameter, then these two
2443 * parameters are made to refer to the same element in args.
2445 * Return the final number of elements in args or -1 if an error has occurred.
2447 int PetScan::extract_nested(__isl_keep isl_space *space,
2448 int n_arg, struct pet_expr **args, std::map<int,int> &param2pos)
2450 int nparam;
2452 nparam = isl_space_dim(space, isl_dim_param);
2453 for (int i = 0; i < nparam; ++i) {
2454 int j;
2455 isl_id *id = isl_space_get_dim_id(space, isl_dim_param, i);
2456 Expr *nested;
2458 if (!is_nested_parameter(id)) {
2459 isl_id_free(id);
2460 continue;
2463 nested = (Expr *) isl_id_get_user(id);
2464 args[n_arg] = extract_expr(nested);
2465 if (!args[n_arg])
2466 return -1;
2468 for (j = 0; j < n_arg; ++j)
2469 if (pet_expr_is_equal(args[j], args[n_arg]))
2470 break;
2472 if (j < n_arg) {
2473 pet_expr_free(args[n_arg]);
2474 args[n_arg] = NULL;
2475 param2pos[i] = j;
2476 } else
2477 param2pos[i] = n_arg++;
2479 isl_id_free(id);
2482 return n_arg;
2485 /* For each nested access parameter in the access relations in "expr",
2486 * construct a corresponding pet_expr, place it in expr->args and
2487 * record its position in "param2pos".
2488 * n is the number of nested access parameters.
2490 struct pet_expr *PetScan::extract_nested(struct pet_expr *expr, int n,
2491 std::map<int,int> &param2pos)
2493 isl_space *space;
2495 expr->args = isl_calloc_array(ctx, struct pet_expr *, n);
2496 expr->n_arg = n;
2497 if (!expr->args)
2498 goto error;
2500 space = isl_map_get_space(expr->acc.access);
2501 n = extract_nested(space, 0, expr->args, param2pos);
2502 isl_space_free(space);
2504 if (n < 0)
2505 goto error;
2507 expr->n_arg = n;
2508 return expr;
2509 error:
2510 pet_expr_free(expr);
2511 return NULL;
2514 /* Look for parameters in any access relation in "expr" that
2515 * refer to nested accesses. In particular, these are
2516 * parameters with no name.
2518 * If there are any such parameters, then the domain of the access
2519 * relation, which is still [] at this point, is replaced by
2520 * [[] -> [t_1,...,t_n]], with n the number of these parameters
2521 * (after identifying identical nested accesses).
2522 * The parameters are then equated to the corresponding t dimensions
2523 * and subsequently projected out.
2524 * param2pos maps the position of the parameter to the position
2525 * of the corresponding t dimension.
2527 struct pet_expr *PetScan::resolve_nested(struct pet_expr *expr)
2529 int n;
2530 int nparam;
2531 int n_in;
2532 isl_space *dim;
2533 isl_map *map;
2534 std::map<int,int> param2pos;
2536 if (!expr)
2537 return expr;
2539 for (int i = 0; i < expr->n_arg; ++i) {
2540 expr->args[i] = resolve_nested(expr->args[i]);
2541 if (!expr->args[i]) {
2542 pet_expr_free(expr);
2543 return NULL;
2547 if (expr->type != pet_expr_access)
2548 return expr;
2550 n = n_nested_parameter(expr->acc.access);
2551 if (n == 0)
2552 return expr;
2554 expr = extract_nested(expr, n, param2pos);
2555 if (!expr)
2556 return NULL;
2558 n = expr->n_arg;
2559 nparam = isl_map_dim(expr->acc.access, isl_dim_param);
2560 n_in = isl_map_dim(expr->acc.access, isl_dim_in);
2561 dim = isl_map_get_space(expr->acc.access);
2562 dim = isl_space_domain(dim);
2563 dim = isl_space_from_domain(dim);
2564 dim = isl_space_add_dims(dim, isl_dim_out, n);
2565 map = isl_map_universe(dim);
2566 map = isl_map_domain_map(map);
2567 map = isl_map_reverse(map);
2568 expr->acc.access = isl_map_apply_domain(expr->acc.access, map);
2570 for (int i = nparam - 1; i >= 0; --i) {
2571 isl_id *id = isl_map_get_dim_id(expr->acc.access,
2572 isl_dim_param, i);
2573 if (!is_nested_parameter(id)) {
2574 isl_id_free(id);
2575 continue;
2578 expr->acc.access = isl_map_equate(expr->acc.access,
2579 isl_dim_param, i, isl_dim_in,
2580 n_in + param2pos[i]);
2581 expr->acc.access = isl_map_project_out(expr->acc.access,
2582 isl_dim_param, i, 1);
2584 isl_id_free(id);
2587 return expr;
2588 error:
2589 pet_expr_free(expr);
2590 return NULL;
2593 /* Convert a top-level pet_expr to a pet_scop with one statement.
2594 * This mainly involves resolving nested expression parameters
2595 * and setting the name of the iteration space.
2596 * The name is given by "label" if it is non-NULL. Otherwise,
2597 * it is of the form S_<n_stmt>.
2599 struct pet_scop *PetScan::extract(Stmt *stmt, struct pet_expr *expr,
2600 __isl_take isl_id *label)
2602 struct pet_stmt *ps;
2603 SourceLocation loc = stmt->getLocStart();
2604 int line = PP.getSourceManager().getExpansionLineNumber(loc);
2606 expr = resolve_nested(expr);
2607 ps = pet_stmt_from_pet_expr(ctx, line, label, n_stmt++, expr);
2608 return pet_scop_from_pet_stmt(ctx, ps);
2611 /* Check if we can extract an affine expression from "expr".
2612 * Return the expressions as an isl_pw_aff if we can and NULL otherwise.
2613 * We turn on autodetection so that we won't generate any warnings
2614 * and turn off nesting, so that we won't accept any non-affine constructs.
2616 __isl_give isl_pw_aff *PetScan::try_extract_affine(Expr *expr)
2618 isl_pw_aff *pwaff;
2619 int save_autodetect = options->autodetect;
2620 bool save_nesting = nesting_enabled;
2622 options->autodetect = 1;
2623 nesting_enabled = false;
2625 pwaff = extract_affine(expr);
2627 options->autodetect = save_autodetect;
2628 nesting_enabled = save_nesting;
2630 return pwaff;
2633 /* Check whether "expr" is an affine expression.
2635 bool PetScan::is_affine(Expr *expr)
2637 isl_pw_aff *pwaff;
2639 pwaff = try_extract_affine(expr);
2640 isl_pw_aff_free(pwaff);
2642 return pwaff != NULL;
2645 /* Check if we can extract an affine constraint from "expr".
2646 * Return the constraint as an isl_set if we can and NULL otherwise.
2647 * We turn on autodetection so that we won't generate any warnings
2648 * and turn off nesting, so that we won't accept any non-affine constructs.
2650 __isl_give isl_pw_aff *PetScan::try_extract_affine_condition(Expr *expr)
2652 isl_pw_aff *cond;
2653 int save_autodetect = options->autodetect;
2654 bool save_nesting = nesting_enabled;
2656 options->autodetect = 1;
2657 nesting_enabled = false;
2659 cond = extract_condition(expr);
2661 options->autodetect = save_autodetect;
2662 nesting_enabled = save_nesting;
2664 return cond;
2667 /* Check whether "expr" is an affine constraint.
2669 bool PetScan::is_affine_condition(Expr *expr)
2671 isl_pw_aff *cond;
2673 cond = try_extract_affine_condition(expr);
2674 isl_pw_aff_free(cond);
2676 return cond != NULL;
2679 /* Check if we can extract a condition from "expr".
2680 * Return the condition as an isl_pw_aff if we can and NULL otherwise.
2681 * If allow_nested is set, then the condition may involve parameters
2682 * corresponding to nested accesses.
2683 * We turn on autodetection so that we won't generate any warnings.
2685 __isl_give isl_pw_aff *PetScan::try_extract_nested_condition(Expr *expr)
2687 isl_pw_aff *cond;
2688 int save_autodetect = options->autodetect;
2689 bool save_nesting = nesting_enabled;
2691 options->autodetect = 1;
2692 nesting_enabled = allow_nested;
2693 cond = extract_condition(expr);
2695 options->autodetect = save_autodetect;
2696 nesting_enabled = save_nesting;
2698 return cond;
2701 /* If the top-level expression of "stmt" is an assignment, then
2702 * return that assignment as a BinaryOperator.
2703 * Otherwise return NULL.
2705 static BinaryOperator *top_assignment_or_null(Stmt *stmt)
2707 BinaryOperator *ass;
2709 if (!stmt)
2710 return NULL;
2711 if (stmt->getStmtClass() != Stmt::BinaryOperatorClass)
2712 return NULL;
2714 ass = cast<BinaryOperator>(stmt);
2715 if(ass->getOpcode() != BO_Assign)
2716 return NULL;
2718 return ass;
2721 /* Check if the given if statement is a conditional assignement
2722 * with a non-affine condition. If so, construct a pet_scop
2723 * corresponding to this conditional assignment. Otherwise return NULL.
2725 * In particular we check if "stmt" is of the form
2727 * if (condition)
2728 * a = f(...);
2729 * else
2730 * a = g(...);
2732 * where a is some array or scalar access.
2733 * The constructed pet_scop then corresponds to the expression
2735 * a = condition ? f(...) : g(...)
2737 * All access relations in f(...) are intersected with condition
2738 * while all access relation in g(...) are intersected with the complement.
2740 struct pet_scop *PetScan::extract_conditional_assignment(IfStmt *stmt)
2742 BinaryOperator *ass_then, *ass_else;
2743 isl_map *write_then, *write_else;
2744 isl_set *cond, *comp;
2745 isl_map *map;
2746 isl_pw_aff *pa;
2747 int equal;
2748 struct pet_expr *pe_cond, *pe_then, *pe_else, *pe, *pe_write;
2749 bool save_nesting = nesting_enabled;
2751 if (!options->detect_conditional_assignment)
2752 return NULL;
2754 ass_then = top_assignment_or_null(stmt->getThen());
2755 ass_else = top_assignment_or_null(stmt->getElse());
2757 if (!ass_then || !ass_else)
2758 return NULL;
2760 if (is_affine_condition(stmt->getCond()))
2761 return NULL;
2763 write_then = extract_access(ass_then->getLHS());
2764 write_else = extract_access(ass_else->getLHS());
2766 equal = isl_map_is_equal(write_then, write_else);
2767 isl_map_free(write_else);
2768 if (equal < 0 || !equal) {
2769 isl_map_free(write_then);
2770 return NULL;
2773 nesting_enabled = allow_nested;
2774 pa = extract_condition(stmt->getCond());
2775 nesting_enabled = save_nesting;
2776 cond = isl_pw_aff_non_zero_set(isl_pw_aff_copy(pa));
2777 comp = isl_pw_aff_zero_set(isl_pw_aff_copy(pa));
2778 map = isl_map_from_range(isl_set_from_pw_aff(pa));
2780 pe_cond = pet_expr_from_access(map);
2782 pe_then = extract_expr(ass_then->getRHS());
2783 pe_then = pet_expr_restrict(pe_then, cond);
2784 pe_else = extract_expr(ass_else->getRHS());
2785 pe_else = pet_expr_restrict(pe_else, comp);
2787 pe = pet_expr_new_ternary(ctx, pe_cond, pe_then, pe_else);
2788 pe_write = pet_expr_from_access(write_then);
2789 if (pe_write) {
2790 pe_write->acc.write = 1;
2791 pe_write->acc.read = 0;
2793 pe = pet_expr_new_binary(ctx, pet_op_assign, pe_write, pe);
2794 return extract(stmt, pe);
2797 /* Create an access to a virtual array representing the result
2798 * of a condition.
2799 * Unlike other accessed data, the id of the array is NULL as
2800 * there is no ValueDecl in the program corresponding to the virtual
2801 * array.
2802 * The array starts out as a scalar, but grows along with the
2803 * statement writing to the array in pet_scop_embed.
2805 static __isl_give isl_map *create_test_access(isl_ctx *ctx, int test_nr)
2807 isl_space *dim = isl_space_alloc(ctx, 0, 0, 0);
2808 isl_id *id;
2809 char name[50];
2811 snprintf(name, sizeof(name), "__pet_test_%d", test_nr);
2812 id = isl_id_alloc(ctx, name, NULL);
2813 dim = isl_space_set_tuple_id(dim, isl_dim_out, id);
2814 return isl_map_universe(dim);
2817 /* Create a pet_scop with a single statement evaluating "cond"
2818 * and writing the result to a virtual scalar, as expressed by
2819 * "access".
2821 struct pet_scop *PetScan::extract_non_affine_condition(Expr *cond,
2822 __isl_take isl_map *access)
2824 struct pet_expr *expr, *write;
2825 struct pet_stmt *ps;
2826 SourceLocation loc = cond->getLocStart();
2827 int line = PP.getSourceManager().getExpansionLineNumber(loc);
2829 write = pet_expr_from_access(access);
2830 if (write) {
2831 write->acc.write = 1;
2832 write->acc.read = 0;
2834 expr = extract_expr(cond);
2835 expr = pet_expr_new_binary(ctx, pet_op_assign, write, expr);
2836 ps = pet_stmt_from_pet_expr(ctx, line, NULL, n_stmt++, expr);
2837 return pet_scop_from_pet_stmt(ctx, ps);
2840 /* Add an array with the given extent ("access") to the list
2841 * of arrays in "scop" and return the extended pet_scop.
2842 * The array is marked as attaining values 0 and 1 only and
2843 * as each element being assigned at most once.
2845 static struct pet_scop *scop_add_array(struct pet_scop *scop,
2846 __isl_keep isl_map *access, clang::ASTContext &ast_ctx)
2848 isl_ctx *ctx = isl_map_get_ctx(access);
2849 isl_space *dim;
2850 struct pet_array **arrays;
2851 struct pet_array *array;
2853 if (!scop)
2854 return NULL;
2855 if (!ctx)
2856 goto error;
2858 arrays = isl_realloc_array(ctx, scop->arrays, struct pet_array *,
2859 scop->n_array + 1);
2860 if (!arrays)
2861 goto error;
2862 scop->arrays = arrays;
2864 array = isl_calloc_type(ctx, struct pet_array);
2865 if (!array)
2866 goto error;
2868 array->extent = isl_map_range(isl_map_copy(access));
2869 dim = isl_space_params_alloc(ctx, 0);
2870 array->context = isl_set_universe(dim);
2871 dim = isl_space_set_alloc(ctx, 0, 1);
2872 array->value_bounds = isl_set_universe(dim);
2873 array->value_bounds = isl_set_lower_bound_si(array->value_bounds,
2874 isl_dim_set, 0, 0);
2875 array->value_bounds = isl_set_upper_bound_si(array->value_bounds,
2876 isl_dim_set, 0, 1);
2877 array->element_type = strdup("int");
2878 array->element_size = ast_ctx.getTypeInfo(ast_ctx.IntTy).first / 8;
2879 array->uniquely_defined = 1;
2881 scop->arrays[scop->n_array] = array;
2882 scop->n_array++;
2884 if (!array->extent || !array->context)
2885 goto error;
2887 return scop;
2888 error:
2889 pet_scop_free(scop);
2890 return NULL;
2893 extern "C" {
2894 static __isl_give isl_map *embed_access(__isl_take isl_map *access,
2895 void *user);
2898 /* Apply the map pointed to by "user" to the domain of the access
2899 * relation, thereby embedding it in the range of the map.
2900 * The domain of both relations is the zero-dimensional domain.
2902 static __isl_give isl_map *embed_access(__isl_take isl_map *access, void *user)
2904 isl_map *map = (isl_map *) user;
2906 return isl_map_apply_domain(access, isl_map_copy(map));
2909 /* Apply "map" to all access relations in "expr".
2911 static struct pet_expr *embed(struct pet_expr *expr, __isl_keep isl_map *map)
2913 return pet_expr_foreach_access(expr, &embed_access, map);
2916 /* How many parameters of "set" refer to nested accesses, i.e., have no name?
2918 static int n_nested_parameter(__isl_keep isl_set *set)
2920 isl_space *space;
2921 int n;
2923 space = isl_set_get_space(set);
2924 n = n_nested_parameter(space);
2925 isl_space_free(space);
2927 return n;
2930 /* Remove all parameters from "map" that refer to nested accesses.
2932 static __isl_give isl_map *remove_nested_parameters(__isl_take isl_map *map)
2934 int nparam;
2935 isl_space *space;
2937 space = isl_map_get_space(map);
2938 nparam = isl_space_dim(space, isl_dim_param);
2939 for (int i = nparam - 1; i >= 0; --i)
2940 if (is_nested_parameter(space, i))
2941 map = isl_map_project_out(map, isl_dim_param, i, 1);
2942 isl_space_free(space);
2944 return map;
2947 extern "C" {
2948 static __isl_give isl_map *access_remove_nested_parameters(
2949 __isl_take isl_map *access, void *user);
2952 static __isl_give isl_map *access_remove_nested_parameters(
2953 __isl_take isl_map *access, void *user)
2955 return remove_nested_parameters(access);
2958 /* Remove all nested access parameters from the schedule and all
2959 * accesses of "stmt".
2960 * There is no need to remove them from the domain as these parameters
2961 * have already been removed from the domain when this function is called.
2963 static struct pet_stmt *remove_nested_parameters(struct pet_stmt *stmt)
2965 if (!stmt)
2966 return NULL;
2967 stmt->schedule = remove_nested_parameters(stmt->schedule);
2968 stmt->body = pet_expr_foreach_access(stmt->body,
2969 &access_remove_nested_parameters, NULL);
2970 if (!stmt->schedule || !stmt->body)
2971 goto error;
2972 for (int i = 0; i < stmt->n_arg; ++i) {
2973 stmt->args[i] = pet_expr_foreach_access(stmt->args[i],
2974 &access_remove_nested_parameters, NULL);
2975 if (!stmt->args[i])
2976 goto error;
2979 return stmt;
2980 error:
2981 pet_stmt_free(stmt);
2982 return NULL;
2985 /* For each nested access parameter in the domain of "stmt",
2986 * construct a corresponding pet_expr, place it in stmt->args and
2987 * record its position in "param2pos".
2988 * n is the number of nested access parameters.
2990 struct pet_stmt *PetScan::extract_nested(struct pet_stmt *stmt, int n,
2991 std::map<int,int> &param2pos)
2993 isl_space *space;
2994 unsigned n_arg;
2995 struct pet_expr **args;
2997 n_arg = stmt->n_arg;
2998 args = isl_realloc_array(ctx, stmt->args, struct pet_expr *, n_arg + n);
2999 if (!args)
3000 goto error;
3001 stmt->args = args;
3002 stmt->n_arg += n;
3004 space = isl_set_get_space(stmt->domain);
3005 n = extract_nested(space, n_arg, stmt->args, param2pos);
3006 isl_space_free(space);
3008 if (n < 0)
3009 goto error;
3011 stmt->n_arg = n;
3012 return stmt;
3013 error:
3014 pet_stmt_free(stmt);
3015 return NULL;
3018 /* Look for parameters in the iteration domain of "stmt" that
3019 * refer to nested accesses. In particular, these are
3020 * parameters with no name.
3022 * If there are any such parameters, then as many extra variables
3023 * (after identifying identical nested accesses) are added to the
3024 * range of the map wrapped inside the domain.
3025 * If the original domain is not a wrapped map, then a new wrapped
3026 * map is created with zero output dimensions.
3027 * The parameters are then equated to the corresponding output dimensions
3028 * and subsequently projected out, from the iteration domain,
3029 * the schedule and the access relations.
3030 * For each of the output dimensions, a corresponding argument
3031 * expression is added. Initially they are created with
3032 * a zero-dimensional domain, so they have to be embedded
3033 * in the current iteration domain.
3034 * param2pos maps the position of the parameter to the position
3035 * of the corresponding output dimension in the wrapped map.
3037 struct pet_stmt *PetScan::resolve_nested(struct pet_stmt *stmt)
3039 int n;
3040 int nparam;
3041 unsigned n_arg;
3042 isl_map *map;
3043 std::map<int,int> param2pos;
3045 if (!stmt)
3046 return NULL;
3048 n = n_nested_parameter(stmt->domain);
3049 if (n == 0)
3050 return stmt;
3052 n_arg = stmt->n_arg;
3053 stmt = extract_nested(stmt, n, param2pos);
3054 if (!stmt)
3055 return NULL;
3057 n = stmt->n_arg - n_arg;
3058 nparam = isl_set_dim(stmt->domain, isl_dim_param);
3059 if (isl_set_is_wrapping(stmt->domain))
3060 map = isl_set_unwrap(stmt->domain);
3061 else
3062 map = isl_map_from_domain(stmt->domain);
3063 map = isl_map_add_dims(map, isl_dim_out, n);
3065 for (int i = nparam - 1; i >= 0; --i) {
3066 isl_id *id;
3068 if (!is_nested_parameter(map, i))
3069 continue;
3071 id = isl_map_get_tuple_id(stmt->args[param2pos[i]]->acc.access,
3072 isl_dim_out);
3073 map = isl_map_set_dim_id(map, isl_dim_out, param2pos[i], id);
3074 map = isl_map_equate(map, isl_dim_param, i, isl_dim_out,
3075 param2pos[i]);
3076 map = isl_map_project_out(map, isl_dim_param, i, 1);
3079 stmt->domain = isl_map_wrap(map);
3081 map = isl_set_unwrap(isl_set_copy(stmt->domain));
3082 map = isl_map_from_range(isl_map_domain(map));
3083 for (int pos = n_arg; pos < stmt->n_arg; ++pos)
3084 stmt->args[pos] = embed(stmt->args[pos], map);
3085 isl_map_free(map);
3087 stmt = remove_nested_parameters(stmt);
3089 return stmt;
3090 error:
3091 pet_stmt_free(stmt);
3092 return NULL;
3095 /* For each statement in "scop", move the parameters that correspond
3096 * to nested access into the ranges of the domains and create
3097 * corresponding argument expressions.
3099 struct pet_scop *PetScan::resolve_nested(struct pet_scop *scop)
3101 if (!scop)
3102 return NULL;
3104 for (int i = 0; i < scop->n_stmt; ++i) {
3105 scop->stmts[i] = resolve_nested(scop->stmts[i]);
3106 if (!scop->stmts[i])
3107 goto error;
3110 return scop;
3111 error:
3112 pet_scop_free(scop);
3113 return NULL;
3116 /* Does "space" involve any parameters that refer to nested
3117 * accesses, i.e., parameters with no name?
3119 static bool has_nested(__isl_keep isl_space *space)
3121 int nparam;
3123 nparam = isl_space_dim(space, isl_dim_param);
3124 for (int i = 0; i < nparam; ++i)
3125 if (is_nested_parameter(space, i))
3126 return true;
3128 return false;
3131 /* Does "pa" involve any parameters that refer to nested
3132 * accesses, i.e., parameters with no name?
3134 static bool has_nested(__isl_keep isl_pw_aff *pa)
3136 isl_space *space;
3137 bool nested;
3139 space = isl_pw_aff_get_space(pa);
3140 nested = has_nested(space);
3141 isl_space_free(space);
3143 return nested;
3146 /* Given an access expression "expr", is the variable accessed by
3147 * "expr" assigned anywhere inside "scop"?
3149 static bool is_assigned(pet_expr *expr, pet_scop *scop)
3151 bool assigned = false;
3152 isl_id *id;
3154 id = isl_map_get_tuple_id(expr->acc.access, isl_dim_out);
3155 assigned = pet_scop_writes(scop, id);
3156 isl_id_free(id);
3158 return assigned;
3161 /* Are all nested access parameters in "pa" allowed given "scop".
3162 * In particular, is none of them written by anywhere inside "scop".
3164 bool PetScan::is_nested_allowed(__isl_keep isl_pw_aff *pa, pet_scop *scop)
3166 int nparam;
3168 nparam = isl_pw_aff_dim(pa, isl_dim_param);
3169 for (int i = 0; i < nparam; ++i) {
3170 Expr *nested;
3171 isl_id *id = isl_pw_aff_get_dim_id(pa, isl_dim_param, i);
3172 pet_expr *expr;
3173 bool allowed;
3175 if (!is_nested_parameter(id)) {
3176 isl_id_free(id);
3177 continue;
3180 nested = (Expr *) isl_id_get_user(id);
3181 expr = extract_expr(nested);
3182 allowed = expr && expr->type == pet_expr_access &&
3183 !is_assigned(expr, scop);
3185 pet_expr_free(expr);
3186 isl_id_free(id);
3188 if (!allowed)
3189 return false;
3192 return true;
3195 /* Construct a pet_scop for an if statement.
3197 * If the condition fits the pattern of a conditional assignment,
3198 * then it is handled by extract_conditional_assignment.
3199 * Otherwise, we do the following.
3201 * If the condition is affine, then the condition is added
3202 * to the iteration domains of the then branch, while the
3203 * opposite of the condition in added to the iteration domains
3204 * of the else branch, if any.
3205 * We allow the condition to be dynamic, i.e., to refer to
3206 * scalars or array elements that may be written to outside
3207 * of the given if statement. These nested accesses are then represented
3208 * as output dimensions in the wrapping iteration domain.
3209 * If it also written _inside_ the then or else branch, then
3210 * we treat the condition as non-affine.
3211 * As explained below, this will introduce an extra statement.
3212 * For aesthetic reasons, we want this statement to have a statement
3213 * number that is lower than those of the then and else branches.
3214 * In order to evaluate if will need such a statement, however, we
3215 * first construct scops for the then and else branches.
3216 * We therefore reserve a statement number if we might have to
3217 * introduce such an extra statement.
3219 * If the condition is not affine, then we create a separate
3220 * statement that writes the result of the condition to a virtual scalar.
3221 * A constraint requiring the value of this virtual scalar to be one
3222 * is added to the iteration domains of the then branch.
3223 * Similarly, a constraint requiring the value of this virtual scalar
3224 * to be zero is added to the iteration domains of the else branch, if any.
3225 * We adjust the schedules to ensure that the virtual scalar is written
3226 * before it is read.
3228 struct pet_scop *PetScan::extract(IfStmt *stmt)
3230 struct pet_scop *scop_then, *scop_else, *scop;
3231 assigned_value_cache cache(assigned_value);
3232 isl_map *test_access = NULL;
3233 isl_pw_aff *cond;
3234 int stmt_id;
3236 scop = extract_conditional_assignment(stmt);
3237 if (scop)
3238 return scop;
3240 cond = try_extract_nested_condition(stmt->getCond());
3241 if (allow_nested && (!cond || has_nested(cond)))
3242 stmt_id = n_stmt++;
3244 scop_then = extract(stmt->getThen());
3246 if (stmt->getElse()) {
3247 scop_else = extract(stmt->getElse());
3248 if (options->autodetect) {
3249 if (scop_then && !scop_else) {
3250 partial = true;
3251 isl_pw_aff_free(cond);
3252 return scop_then;
3254 if (!scop_then && scop_else) {
3255 partial = true;
3256 isl_pw_aff_free(cond);
3257 return scop_else;
3262 if (cond &&
3263 (!is_nested_allowed(cond, scop_then) ||
3264 (stmt->getElse() && !is_nested_allowed(cond, scop_else)))) {
3265 isl_pw_aff_free(cond);
3266 cond = NULL;
3268 if (allow_nested && !cond) {
3269 int save_n_stmt = n_stmt;
3270 test_access = create_test_access(ctx, n_test++);
3271 n_stmt = stmt_id;
3272 scop = extract_non_affine_condition(stmt->getCond(),
3273 isl_map_copy(test_access));
3274 n_stmt = save_n_stmt;
3275 scop = scop_add_array(scop, test_access, ast_context);
3276 if (!scop) {
3277 pet_scop_free(scop_then);
3278 pet_scop_free(scop_else);
3279 isl_map_free(test_access);
3280 return NULL;
3284 if (!scop) {
3285 isl_set *set;
3286 isl_set *valid;
3288 if (!cond)
3289 cond = extract_condition(stmt->getCond());
3290 valid = isl_pw_aff_domain(isl_pw_aff_copy(cond));
3291 set = isl_pw_aff_non_zero_set(cond);
3292 scop = pet_scop_restrict(scop_then, isl_set_copy(set));
3294 if (stmt->getElse()) {
3295 set = isl_set_subtract(isl_set_copy(valid), set);
3296 scop_else = pet_scop_restrict(scop_else, set);
3297 scop = pet_scop_add(ctx, scop, scop_else);
3298 } else
3299 isl_set_free(set);
3300 scop = resolve_nested(scop);
3301 scop = pet_scop_restrict_context(scop, valid);
3302 } else {
3303 scop = pet_scop_prefix(scop, 0);
3304 scop_then = pet_scop_prefix(scop_then, 1);
3305 scop_then = pet_scop_filter(scop_then,
3306 isl_map_copy(test_access), 1);
3307 scop = pet_scop_add(ctx, scop, scop_then);
3308 if (stmt->getElse()) {
3309 scop_else = pet_scop_prefix(scop_else, 1);
3310 scop_else = pet_scop_filter(scop_else, test_access, 0);
3311 scop = pet_scop_add(ctx, scop, scop_else);
3312 } else
3313 isl_map_free(test_access);
3316 return scop;
3319 /* Try and construct a pet_scop for a label statement.
3320 * We currently only allow labels on expression statements.
3322 struct pet_scop *PetScan::extract(LabelStmt *stmt)
3324 isl_id *label;
3325 Stmt *sub;
3327 sub = stmt->getSubStmt();
3328 if (!isa<Expr>(sub)) {
3329 unsupported(stmt);
3330 return NULL;
3333 label = isl_id_alloc(ctx, stmt->getName(), NULL);
3335 return extract(sub, extract_expr(cast<Expr>(sub)), label);
3338 /* Try and construct a pet_scop corresponding to "stmt".
3340 struct pet_scop *PetScan::extract(Stmt *stmt)
3342 if (isa<Expr>(stmt))
3343 return extract(stmt, extract_expr(cast<Expr>(stmt)));
3345 switch (stmt->getStmtClass()) {
3346 case Stmt::WhileStmtClass:
3347 return extract(cast<WhileStmt>(stmt));
3348 case Stmt::ForStmtClass:
3349 return extract_for(cast<ForStmt>(stmt));
3350 case Stmt::IfStmtClass:
3351 return extract(cast<IfStmt>(stmt));
3352 case Stmt::CompoundStmtClass:
3353 return extract(cast<CompoundStmt>(stmt));
3354 case Stmt::LabelStmtClass:
3355 return extract(cast<LabelStmt>(stmt));
3356 default:
3357 unsupported(stmt);
3360 return NULL;
3363 /* Try and construct a pet_scop corresponding to (part of)
3364 * a sequence of statements.
3366 struct pet_scop *PetScan::extract(StmtRange stmt_range)
3368 pet_scop *scop;
3369 StmtIterator i;
3370 int j;
3371 bool partial_range = false;
3373 scop = pet_scop_empty(ctx);
3374 for (i = stmt_range.first, j = 0; i != stmt_range.second; ++i, ++j) {
3375 Stmt *child = *i;
3376 struct pet_scop *scop_i;
3377 scop_i = extract(child);
3378 if (scop && partial) {
3379 pet_scop_free(scop_i);
3380 break;
3382 scop_i = pet_scop_prefix(scop_i, j);
3383 if (options->autodetect) {
3384 if (scop_i)
3385 scop = pet_scop_add(ctx, scop, scop_i);
3386 else
3387 partial_range = true;
3388 if (scop->n_stmt != 0 && !scop_i)
3389 partial = true;
3390 } else {
3391 scop = pet_scop_add(ctx, scop, scop_i);
3393 if (partial)
3394 break;
3397 if (scop && partial_range)
3398 partial = true;
3400 return scop;
3403 /* Check if the scop marked by the user is exactly this Stmt
3404 * or part of this Stmt.
3405 * If so, return a pet_scop corresponding to the marked region.
3406 * Otherwise, return NULL.
3408 struct pet_scop *PetScan::scan(Stmt *stmt)
3410 SourceManager &SM = PP.getSourceManager();
3411 unsigned start_off, end_off;
3413 start_off = SM.getFileOffset(stmt->getLocStart());
3414 end_off = SM.getFileOffset(stmt->getLocEnd());
3416 if (start_off > loc.end)
3417 return NULL;
3418 if (end_off < loc.start)
3419 return NULL;
3420 if (start_off >= loc.start && end_off <= loc.end) {
3421 return extract(stmt);
3424 StmtIterator start;
3425 for (start = stmt->child_begin(); start != stmt->child_end(); ++start) {
3426 Stmt *child = *start;
3427 if (!child)
3428 continue;
3429 start_off = SM.getFileOffset(child->getLocStart());
3430 end_off = SM.getFileOffset(child->getLocEnd());
3431 if (start_off < loc.start && end_off > loc.end)
3432 return scan(child);
3433 if (start_off >= loc.start)
3434 break;
3437 StmtIterator end;
3438 for (end = start; end != stmt->child_end(); ++end) {
3439 Stmt *child = *end;
3440 start_off = SM.getFileOffset(child->getLocStart());
3441 if (start_off >= loc.end)
3442 break;
3445 return extract(StmtRange(start, end));
3448 /* Set the size of index "pos" of "array" to "size".
3449 * In particular, add a constraint of the form
3451 * i_pos < size
3453 * to array->extent and a constraint of the form
3455 * size >= 0
3457 * to array->context.
3459 static struct pet_array *update_size(struct pet_array *array, int pos,
3460 __isl_take isl_pw_aff *size)
3462 isl_set *valid;
3463 isl_set *univ;
3464 isl_set *bound;
3465 isl_space *dim;
3466 isl_aff *aff;
3467 isl_pw_aff *index;
3468 isl_id *id;
3470 valid = isl_pw_aff_nonneg_set(isl_pw_aff_copy(size));
3471 array->context = isl_set_intersect(array->context, valid);
3473 dim = isl_set_get_space(array->extent);
3474 aff = isl_aff_zero_on_domain(isl_local_space_from_space(dim));
3475 aff = isl_aff_add_coefficient_si(aff, isl_dim_in, pos, 1);
3476 univ = isl_set_universe(isl_aff_get_domain_space(aff));
3477 index = isl_pw_aff_alloc(univ, aff);
3479 size = isl_pw_aff_add_dims(size, isl_dim_in,
3480 isl_set_dim(array->extent, isl_dim_set));
3481 id = isl_set_get_tuple_id(array->extent);
3482 size = isl_pw_aff_set_tuple_id(size, isl_dim_in, id);
3483 bound = isl_pw_aff_lt_set(index, size);
3485 array->extent = isl_set_intersect(array->extent, bound);
3487 if (!array->context || !array->extent)
3488 goto error;
3490 return array;
3491 error:
3492 pet_array_free(array);
3493 return NULL;
3496 /* Figure out the size of the array at position "pos" and all
3497 * subsequent positions from "type" and update "array" accordingly.
3499 struct pet_array *PetScan::set_upper_bounds(struct pet_array *array,
3500 const Type *type, int pos)
3502 const ArrayType *atype;
3503 isl_pw_aff *size;
3505 if (!array)
3506 return NULL;
3508 if (type->isPointerType()) {
3509 type = type->getPointeeType().getTypePtr();
3510 return set_upper_bounds(array, type, pos + 1);
3512 if (!type->isArrayType())
3513 return array;
3515 type = type->getCanonicalTypeInternal().getTypePtr();
3516 atype = cast<ArrayType>(type);
3518 if (type->isConstantArrayType()) {
3519 const ConstantArrayType *ca = cast<ConstantArrayType>(atype);
3520 size = extract_affine(ca->getSize());
3521 array = update_size(array, pos, size);
3522 } else if (type->isVariableArrayType()) {
3523 const VariableArrayType *vla = cast<VariableArrayType>(atype);
3524 size = extract_affine(vla->getSizeExpr());
3525 array = update_size(array, pos, size);
3528 type = atype->getElementType().getTypePtr();
3530 return set_upper_bounds(array, type, pos + 1);
3533 /* Construct and return a pet_array corresponding to the variable "decl".
3534 * In particular, initialize array->extent to
3536 * { name[i_1,...,i_d] : i_1,...,i_d >= 0 }
3538 * and then call set_upper_bounds to set the upper bounds on the indices
3539 * based on the type of the variable.
3541 struct pet_array *PetScan::extract_array(isl_ctx *ctx, ValueDecl *decl)
3543 struct pet_array *array;
3544 QualType qt = decl->getType();
3545 const Type *type = qt.getTypePtr();
3546 int depth = array_depth(type);
3547 QualType base = base_type(qt);
3548 string name;
3549 isl_id *id;
3550 isl_space *dim;
3552 array = isl_calloc_type(ctx, struct pet_array);
3553 if (!array)
3554 return NULL;
3556 id = isl_id_alloc(ctx, decl->getName().str().c_str(), decl);
3557 dim = isl_space_set_alloc(ctx, 0, depth);
3558 dim = isl_space_set_tuple_id(dim, isl_dim_set, id);
3560 array->extent = isl_set_nat_universe(dim);
3562 dim = isl_space_params_alloc(ctx, 0);
3563 array->context = isl_set_universe(dim);
3565 array = set_upper_bounds(array, type, 0);
3566 if (!array)
3567 return NULL;
3569 name = base.getAsString();
3570 array->element_type = strdup(name.c_str());
3571 array->element_size = decl->getASTContext().getTypeInfo(base).first / 8;
3573 return array;
3576 /* Construct a list of pet_arrays, one for each array (or scalar)
3577 * accessed inside "scop" add this list to "scop" and return the result.
3579 * The context of "scop" is updated with the intesection of
3580 * the contexts of all arrays, i.e., constraints on the parameters
3581 * that ensure that the arrays have a valid (non-negative) size.
3583 struct pet_scop *PetScan::scan_arrays(struct pet_scop *scop)
3585 int i;
3586 set<ValueDecl *> arrays;
3587 set<ValueDecl *>::iterator it;
3588 int n_array;
3589 struct pet_array **scop_arrays;
3591 if (!scop)
3592 return NULL;
3594 pet_scop_collect_arrays(scop, arrays);
3595 if (arrays.size() == 0)
3596 return scop;
3598 n_array = scop->n_array;
3600 scop_arrays = isl_realloc_array(ctx, scop->arrays, struct pet_array *,
3601 n_array + arrays.size());
3602 if (!scop_arrays)
3603 goto error;
3604 scop->arrays = scop_arrays;
3606 for (it = arrays.begin(), i = 0; it != arrays.end(); ++it, ++i) {
3607 struct pet_array *array;
3608 scop->arrays[n_array + i] = array = extract_array(ctx, *it);
3609 if (!scop->arrays[n_array + i])
3610 goto error;
3611 scop->n_array++;
3612 scop->context = isl_set_intersect(scop->context,
3613 isl_set_copy(array->context));
3614 if (!scop->context)
3615 goto error;
3618 return scop;
3619 error:
3620 pet_scop_free(scop);
3621 return NULL;
3624 /* Bound all parameters in scop->context to the possible values
3625 * of the corresponding C variable.
3627 static struct pet_scop *add_parameter_bounds(struct pet_scop *scop)
3629 int n;
3631 if (!scop)
3632 return NULL;
3634 n = isl_set_dim(scop->context, isl_dim_param);
3635 for (int i = 0; i < n; ++i) {
3636 isl_id *id;
3637 ValueDecl *decl;
3639 id = isl_set_get_dim_id(scop->context, isl_dim_param, i);
3640 decl = (ValueDecl *) isl_id_get_user(id);
3641 isl_id_free(id);
3643 scop->context = set_parameter_bounds(scop->context, i, decl);
3645 if (!scop->context)
3646 goto error;
3649 return scop;
3650 error:
3651 pet_scop_free(scop);
3652 return NULL;
3655 /* Construct a pet_scop from the given function.
3657 struct pet_scop *PetScan::scan(FunctionDecl *fd)
3659 pet_scop *scop;
3660 Stmt *stmt;
3662 stmt = fd->getBody();
3664 if (options->autodetect)
3665 scop = extract(stmt);
3666 else
3667 scop = scan(stmt);
3668 scop = pet_scop_detect_parameter_accesses(scop);
3669 scop = scan_arrays(scop);
3670 scop = add_parameter_bounds(scop);
3671 scop = pet_scop_gist(scop, value_bounds);
3673 return scop;