PetScan::extract_non_affine_condition: remove redundant resolve_nested
[pet.git] / scan.cc
blobb807d69c58f3e907af7474571f8358ce2bd86b51
1 /*
2 * Copyright 2011 Leiden University. All rights reserved.
3 * Copyright 2012-2014 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 <string.h>
36 #include <set>
37 #include <map>
38 #include <iostream>
39 #include <llvm/Support/raw_ostream.h>
40 #include <clang/AST/ASTContext.h>
41 #include <clang/AST/ASTDiagnostic.h>
42 #include <clang/AST/Expr.h>
43 #include <clang/AST/RecursiveASTVisitor.h>
45 #include <isl/id.h>
46 #include <isl/space.h>
47 #include <isl/aff.h>
48 #include <isl/set.h>
50 #include "clang.h"
51 #include "options.h"
52 #include "scan.h"
53 #include "scop.h"
54 #include "scop_plus.h"
56 #include "config.h"
58 using namespace std;
59 using namespace clang;
61 #if defined(DECLREFEXPR_CREATE_REQUIRES_BOOL)
62 static DeclRefExpr *create_DeclRefExpr(VarDecl *var)
64 return DeclRefExpr::Create(var->getASTContext(), var->getQualifierLoc(),
65 SourceLocation(), var, false, var->getInnerLocStart(),
66 var->getType(), VK_LValue);
68 #elif defined(DECLREFEXPR_CREATE_REQUIRES_SOURCELOCATION)
69 static DeclRefExpr *create_DeclRefExpr(VarDecl *var)
71 return DeclRefExpr::Create(var->getASTContext(), var->getQualifierLoc(),
72 SourceLocation(), var, var->getInnerLocStart(), var->getType(),
73 VK_LValue);
75 #else
76 static DeclRefExpr *create_DeclRefExpr(VarDecl *var)
78 return DeclRefExpr::Create(var->getASTContext(), var->getQualifierLoc(),
79 var, var->getInnerLocStart(), var->getType(), VK_LValue);
81 #endif
83 /* Check if the element type corresponding to the given array type
84 * has a const qualifier.
86 static bool const_base(QualType qt)
88 const Type *type = qt.getTypePtr();
90 if (type->isPointerType())
91 return const_base(type->getPointeeType());
92 if (type->isArrayType()) {
93 const ArrayType *atype;
94 type = type->getCanonicalTypeInternal().getTypePtr();
95 atype = cast<ArrayType>(type);
96 return const_base(atype->getElementType());
99 return qt.isConstQualified();
102 /* Mark "decl" as having an unknown value in "assigned_value".
104 * If no (known or unknown) value was assigned to "decl" before,
105 * then it may have been treated as a parameter before and may
106 * therefore appear in a value assigned to another variable.
107 * If so, this assignment needs to be turned into an unknown value too.
109 static void clear_assignment(map<ValueDecl *, isl_pw_aff *> &assigned_value,
110 ValueDecl *decl)
112 map<ValueDecl *, isl_pw_aff *>::iterator it;
114 it = assigned_value.find(decl);
116 assigned_value[decl] = NULL;
118 if (it != assigned_value.end())
119 return;
121 for (it = assigned_value.begin(); it != assigned_value.end(); ++it) {
122 isl_pw_aff *pa = it->second;
123 int nparam = isl_pw_aff_dim(pa, isl_dim_param);
125 for (int i = 0; i < nparam; ++i) {
126 isl_id *id;
128 if (!isl_pw_aff_has_dim_id(pa, isl_dim_param, i))
129 continue;
130 id = isl_pw_aff_get_dim_id(pa, isl_dim_param, i);
131 if (isl_id_get_user(id) == decl)
132 it->second = NULL;
133 isl_id_free(id);
138 /* Look for any assignments to scalar variables in part of the parse
139 * tree and set assigned_value to NULL for each of them.
140 * Also reset assigned_value if the address of a scalar variable
141 * is being taken. As an exception, if the address is passed to a function
142 * that is declared to receive a const pointer, then assigned_value is
143 * not reset.
145 * This ensures that we won't use any previously stored value
146 * in the current subtree and its parents.
148 struct clear_assignments : RecursiveASTVisitor<clear_assignments> {
149 map<ValueDecl *, isl_pw_aff *> &assigned_value;
150 set<UnaryOperator *> skip;
152 clear_assignments(map<ValueDecl *, isl_pw_aff *> &assigned_value) :
153 assigned_value(assigned_value) {}
155 /* Check for "address of" operators whose value is passed
156 * to a const pointer argument and add them to "skip", so that
157 * we can skip them in VisitUnaryOperator.
159 bool VisitCallExpr(CallExpr *expr) {
160 FunctionDecl *fd;
161 fd = expr->getDirectCallee();
162 if (!fd)
163 return true;
164 for (int i = 0; i < expr->getNumArgs(); ++i) {
165 Expr *arg = expr->getArg(i);
166 UnaryOperator *op;
167 if (arg->getStmtClass() == Stmt::ImplicitCastExprClass) {
168 ImplicitCastExpr *ice;
169 ice = cast<ImplicitCastExpr>(arg);
170 arg = ice->getSubExpr();
172 if (arg->getStmtClass() != Stmt::UnaryOperatorClass)
173 continue;
174 op = cast<UnaryOperator>(arg);
175 if (op->getOpcode() != UO_AddrOf)
176 continue;
177 if (const_base(fd->getParamDecl(i)->getType()))
178 skip.insert(op);
180 return true;
183 bool VisitUnaryOperator(UnaryOperator *expr) {
184 Expr *arg;
185 DeclRefExpr *ref;
186 ValueDecl *decl;
188 switch (expr->getOpcode()) {
189 case UO_AddrOf:
190 case UO_PostInc:
191 case UO_PostDec:
192 case UO_PreInc:
193 case UO_PreDec:
194 break;
195 default:
196 return true;
198 if (skip.find(expr) != skip.end())
199 return true;
201 arg = expr->getSubExpr();
202 if (arg->getStmtClass() != Stmt::DeclRefExprClass)
203 return true;
204 ref = cast<DeclRefExpr>(arg);
205 decl = ref->getDecl();
206 clear_assignment(assigned_value, decl);
207 return true;
210 bool VisitBinaryOperator(BinaryOperator *expr) {
211 Expr *lhs;
212 DeclRefExpr *ref;
213 ValueDecl *decl;
215 if (!expr->isAssignmentOp())
216 return true;
217 lhs = expr->getLHS();
218 if (lhs->getStmtClass() != Stmt::DeclRefExprClass)
219 return true;
220 ref = cast<DeclRefExpr>(lhs);
221 decl = ref->getDecl();
222 clear_assignment(assigned_value, decl);
223 return true;
227 /* Keep a copy of the currently assigned values.
229 * Any variable that is assigned a value inside the current scope
230 * is removed again when we leave the scope (either because it wasn't
231 * stored in the cache or because it has a different value in the cache).
233 struct assigned_value_cache {
234 map<ValueDecl *, isl_pw_aff *> &assigned_value;
235 map<ValueDecl *, isl_pw_aff *> cache;
237 assigned_value_cache(map<ValueDecl *, isl_pw_aff *> &assigned_value) :
238 assigned_value(assigned_value), cache(assigned_value) {}
239 ~assigned_value_cache() {
240 map<ValueDecl *, isl_pw_aff *>::iterator it = cache.begin();
241 for (it = assigned_value.begin(); it != assigned_value.end();
242 ++it) {
243 if (!it->second ||
244 (cache.find(it->first) != cache.end() &&
245 cache[it->first] != it->second))
246 cache[it->first] = NULL;
248 assigned_value = cache;
252 /* Insert an expression into the collection of expressions,
253 * provided it is not already in there.
254 * The isl_pw_affs are freed in the destructor.
256 void PetScan::insert_expression(__isl_take isl_pw_aff *expr)
258 std::set<isl_pw_aff *>::iterator it;
260 if (expressions.find(expr) == expressions.end())
261 expressions.insert(expr);
262 else
263 isl_pw_aff_free(expr);
266 PetScan::~PetScan()
268 std::set<isl_pw_aff *>::iterator it;
270 for (it = expressions.begin(); it != expressions.end(); ++it)
271 isl_pw_aff_free(*it);
273 isl_union_map_free(value_bounds);
276 /* Report a diagnostic, unless autodetect is set.
278 void PetScan::report(Stmt *stmt, unsigned id)
280 if (options->autodetect)
281 return;
283 SourceLocation loc = stmt->getLocStart();
284 DiagnosticsEngine &diag = PP.getDiagnostics();
285 DiagnosticBuilder B = diag.Report(loc, id) << stmt->getSourceRange();
288 /* Called if we found something we (currently) cannot handle.
289 * We'll provide more informative warnings later.
291 * We only actually complain if autodetect is false.
293 void PetScan::unsupported(Stmt *stmt)
295 DiagnosticsEngine &diag = PP.getDiagnostics();
296 unsigned id = diag.getCustomDiagID(DiagnosticsEngine::Warning,
297 "unsupported");
298 report(stmt, id);
301 /* Report a missing prototype, unless autodetect is set.
303 void PetScan::report_prototype_required(Stmt *stmt)
305 DiagnosticsEngine &diag = PP.getDiagnostics();
306 unsigned id = diag.getCustomDiagID(DiagnosticsEngine::Warning,
307 "prototype required");
308 report(stmt, id);
311 /* Extract an integer from "expr".
313 __isl_give isl_val *PetScan::extract_int(isl_ctx *ctx, IntegerLiteral *expr)
315 const Type *type = expr->getType().getTypePtr();
316 int is_signed = type->hasSignedIntegerRepresentation();
317 llvm::APInt val = expr->getValue();
318 int is_negative = is_signed && val.isNegative();
319 isl_val *v;
321 if (is_negative)
322 val = -val;
324 v = extract_unsigned(ctx, val);
326 if (is_negative)
327 v = isl_val_neg(v);
328 return v;
331 /* Extract an integer from "val", which assumed to be non-negative.
333 __isl_give isl_val *PetScan::extract_unsigned(isl_ctx *ctx,
334 const llvm::APInt &val)
336 unsigned n;
337 const uint64_t *data;
339 data = val.getRawData();
340 n = val.getNumWords();
341 return isl_val_int_from_chunks(ctx, n, sizeof(uint64_t), data);
344 /* Extract an integer from "expr".
345 * Return NULL if "expr" does not (obviously) represent an integer.
347 __isl_give isl_val *PetScan::extract_int(clang::ParenExpr *expr)
349 return extract_int(expr->getSubExpr());
352 /* Extract an integer from "expr".
353 * Return NULL if "expr" does not (obviously) represent an integer.
355 __isl_give isl_val *PetScan::extract_int(clang::Expr *expr)
357 if (expr->getStmtClass() == Stmt::IntegerLiteralClass)
358 return extract_int(ctx, cast<IntegerLiteral>(expr));
359 if (expr->getStmtClass() == Stmt::ParenExprClass)
360 return extract_int(cast<ParenExpr>(expr));
362 unsupported(expr);
363 return NULL;
366 /* Extract an affine expression from the IntegerLiteral "expr".
368 __isl_give isl_pw_aff *PetScan::extract_affine(IntegerLiteral *expr)
370 isl_space *dim = isl_space_params_alloc(ctx, 0);
371 isl_local_space *ls = isl_local_space_from_space(isl_space_copy(dim));
372 isl_aff *aff = isl_aff_zero_on_domain(ls);
373 isl_set *dom = isl_set_universe(dim);
374 isl_val *v;
376 v = extract_int(expr);
377 aff = isl_aff_add_constant_val(aff, v);
379 return isl_pw_aff_alloc(dom, aff);
382 /* Extract an affine expression from the APInt "val", which is assumed
383 * to be non-negative.
385 __isl_give isl_pw_aff *PetScan::extract_affine(const llvm::APInt &val)
387 isl_space *dim = isl_space_params_alloc(ctx, 0);
388 isl_local_space *ls = isl_local_space_from_space(isl_space_copy(dim));
389 isl_aff *aff = isl_aff_zero_on_domain(ls);
390 isl_set *dom = isl_set_universe(dim);
391 isl_val *v;
393 v = extract_unsigned(ctx, val);
394 aff = isl_aff_add_constant_val(aff, v);
396 return isl_pw_aff_alloc(dom, aff);
399 __isl_give isl_pw_aff *PetScan::extract_affine(ImplicitCastExpr *expr)
401 return extract_affine(expr->getSubExpr());
404 static unsigned get_type_size(ValueDecl *decl)
406 return decl->getASTContext().getIntWidth(decl->getType());
409 /* Bound parameter "pos" of "set" to the possible values of "decl".
411 static __isl_give isl_set *set_parameter_bounds(__isl_take isl_set *set,
412 unsigned pos, ValueDecl *decl)
414 unsigned width;
415 isl_ctx *ctx;
416 isl_val *bound;
418 ctx = isl_set_get_ctx(set);
419 width = get_type_size(decl);
420 if (decl->getType()->isUnsignedIntegerType()) {
421 set = isl_set_lower_bound_si(set, isl_dim_param, pos, 0);
422 bound = isl_val_int_from_ui(ctx, width);
423 bound = isl_val_2exp(bound);
424 bound = isl_val_sub_ui(bound, 1);
425 set = isl_set_upper_bound_val(set, isl_dim_param, pos, bound);
426 } else {
427 bound = isl_val_int_from_ui(ctx, width - 1);
428 bound = isl_val_2exp(bound);
429 bound = isl_val_sub_ui(bound, 1);
430 set = isl_set_upper_bound_val(set, isl_dim_param, pos,
431 isl_val_copy(bound));
432 bound = isl_val_neg(bound);
433 bound = isl_val_sub_ui(bound, 1);
434 set = isl_set_lower_bound_val(set, isl_dim_param, pos, bound);
437 return set;
440 /* Extract an affine expression from the DeclRefExpr "expr".
442 * If the variable has been assigned a value, then we check whether
443 * we know what (affine) value was assigned.
444 * If so, we return this value. Otherwise we convert "expr"
445 * to an extra parameter (provided nesting_enabled is set).
447 * Otherwise, we simply return an expression that is equal
448 * to a parameter corresponding to the referenced variable.
450 __isl_give isl_pw_aff *PetScan::extract_affine(DeclRefExpr *expr)
452 ValueDecl *decl = expr->getDecl();
453 const Type *type = decl->getType().getTypePtr();
454 isl_id *id;
455 isl_space *dim;
456 isl_aff *aff;
457 isl_set *dom;
459 if (!type->isIntegerType()) {
460 unsupported(expr);
461 return NULL;
464 if (assigned_value.find(decl) != assigned_value.end()) {
465 if (assigned_value[decl])
466 return isl_pw_aff_copy(assigned_value[decl]);
467 else
468 return nested_access(expr);
471 id = isl_id_alloc(ctx, decl->getName().str().c_str(), decl);
472 dim = isl_space_params_alloc(ctx, 1);
474 dim = isl_space_set_dim_id(dim, isl_dim_param, 0, id);
476 dom = isl_set_universe(isl_space_copy(dim));
477 aff = isl_aff_zero_on_domain(isl_local_space_from_space(dim));
478 aff = isl_aff_add_coefficient_si(aff, isl_dim_param, 0, 1);
480 return isl_pw_aff_alloc(dom, aff);
483 /* Extract an affine expression from an integer division operation.
484 * In particular, if "expr" is lhs/rhs, then return
486 * lhs >= 0 ? floor(lhs/rhs) : ceil(lhs/rhs)
488 * The second argument (rhs) is required to be a (positive) integer constant.
490 __isl_give isl_pw_aff *PetScan::extract_affine_div(BinaryOperator *expr)
492 int is_cst;
493 isl_pw_aff *rhs, *lhs;
495 rhs = extract_affine(expr->getRHS());
496 is_cst = isl_pw_aff_is_cst(rhs);
497 if (is_cst < 0 || !is_cst) {
498 isl_pw_aff_free(rhs);
499 if (!is_cst)
500 unsupported(expr);
501 return NULL;
504 lhs = extract_affine(expr->getLHS());
506 return isl_pw_aff_tdiv_q(lhs, rhs);
509 /* Extract an affine expression from a modulo operation.
510 * In particular, if "expr" is lhs/rhs, then return
512 * lhs - rhs * (lhs >= 0 ? floor(lhs/rhs) : ceil(lhs/rhs))
514 * The second argument (rhs) is required to be a (positive) integer constant.
516 __isl_give isl_pw_aff *PetScan::extract_affine_mod(BinaryOperator *expr)
518 int is_cst;
519 isl_pw_aff *rhs, *lhs;
521 rhs = extract_affine(expr->getRHS());
522 is_cst = isl_pw_aff_is_cst(rhs);
523 if (is_cst < 0 || !is_cst) {
524 isl_pw_aff_free(rhs);
525 if (!is_cst)
526 unsupported(expr);
527 return NULL;
530 lhs = extract_affine(expr->getLHS());
532 return isl_pw_aff_tdiv_r(lhs, rhs);
535 /* Extract an affine expression from a multiplication operation.
536 * This is only allowed if at least one of the two arguments
537 * is a (piecewise) constant.
539 __isl_give isl_pw_aff *PetScan::extract_affine_mul(BinaryOperator *expr)
541 isl_pw_aff *lhs;
542 isl_pw_aff *rhs;
544 lhs = extract_affine(expr->getLHS());
545 rhs = extract_affine(expr->getRHS());
547 if (!isl_pw_aff_is_cst(lhs) && !isl_pw_aff_is_cst(rhs)) {
548 isl_pw_aff_free(lhs);
549 isl_pw_aff_free(rhs);
550 unsupported(expr);
551 return NULL;
554 return isl_pw_aff_mul(lhs, rhs);
557 /* Extract an affine expression from an addition or subtraction operation.
559 __isl_give isl_pw_aff *PetScan::extract_affine_add(BinaryOperator *expr)
561 isl_pw_aff *lhs;
562 isl_pw_aff *rhs;
564 lhs = extract_affine(expr->getLHS());
565 rhs = extract_affine(expr->getRHS());
567 switch (expr->getOpcode()) {
568 case BO_Add:
569 return isl_pw_aff_add(lhs, rhs);
570 case BO_Sub:
571 return isl_pw_aff_sub(lhs, rhs);
572 default:
573 isl_pw_aff_free(lhs);
574 isl_pw_aff_free(rhs);
575 return NULL;
580 /* Compute
582 * pwaff mod 2^width
584 static __isl_give isl_pw_aff *wrap(__isl_take isl_pw_aff *pwaff,
585 unsigned width)
587 isl_ctx *ctx;
588 isl_val *mod;
590 ctx = isl_pw_aff_get_ctx(pwaff);
591 mod = isl_val_int_from_ui(ctx, width);
592 mod = isl_val_2exp(mod);
594 pwaff = isl_pw_aff_mod_val(pwaff, mod);
596 return pwaff;
599 /* Limit the domain of "pwaff" to those elements where the function
600 * value satisfies
602 * 2^{width-1} <= pwaff < 2^{width-1}
604 static __isl_give isl_pw_aff *avoid_overflow(__isl_take isl_pw_aff *pwaff,
605 unsigned width)
607 isl_ctx *ctx;
608 isl_val *v;
609 isl_space *space = isl_pw_aff_get_domain_space(pwaff);
610 isl_local_space *ls = isl_local_space_from_space(space);
611 isl_aff *bound;
612 isl_set *dom;
613 isl_pw_aff *b;
615 ctx = isl_pw_aff_get_ctx(pwaff);
616 v = isl_val_int_from_ui(ctx, width - 1);
617 v = isl_val_2exp(v);
619 bound = isl_aff_zero_on_domain(ls);
620 bound = isl_aff_add_constant_val(bound, v);
621 b = isl_pw_aff_from_aff(bound);
623 dom = isl_pw_aff_lt_set(isl_pw_aff_copy(pwaff), isl_pw_aff_copy(b));
624 pwaff = isl_pw_aff_intersect_domain(pwaff, dom);
626 b = isl_pw_aff_neg(b);
627 dom = isl_pw_aff_ge_set(isl_pw_aff_copy(pwaff), b);
628 pwaff = isl_pw_aff_intersect_domain(pwaff, dom);
630 return pwaff;
633 /* Handle potential overflows on signed computations.
635 * If options->signed_overflow is set to PET_OVERFLOW_AVOID,
636 * the we adjust the domain of "pa" to avoid overflows.
638 __isl_give isl_pw_aff *PetScan::signed_overflow(__isl_take isl_pw_aff *pa,
639 unsigned width)
641 if (options->signed_overflow == PET_OVERFLOW_AVOID)
642 pa = avoid_overflow(pa, width);
644 return pa;
647 /* Return the piecewise affine expression "set ? 1 : 0" defined on "dom".
649 static __isl_give isl_pw_aff *indicator_function(__isl_take isl_set *set,
650 __isl_take isl_set *dom)
652 isl_pw_aff *pa;
653 pa = isl_set_indicator_function(set);
654 pa = isl_pw_aff_intersect_domain(pa, dom);
655 return pa;
658 /* Extract an affine expression from some binary operations.
659 * If the result of the expression is unsigned, then we wrap it
660 * based on the size of the type. Otherwise, we ensure that
661 * no overflow occurs.
663 __isl_give isl_pw_aff *PetScan::extract_affine(BinaryOperator *expr)
665 isl_pw_aff *res;
666 unsigned width;
668 switch (expr->getOpcode()) {
669 case BO_Add:
670 case BO_Sub:
671 res = extract_affine_add(expr);
672 break;
673 case BO_Div:
674 res = extract_affine_div(expr);
675 break;
676 case BO_Rem:
677 res = extract_affine_mod(expr);
678 break;
679 case BO_Mul:
680 res = extract_affine_mul(expr);
681 break;
682 case BO_LT:
683 case BO_LE:
684 case BO_GT:
685 case BO_GE:
686 case BO_EQ:
687 case BO_NE:
688 case BO_LAnd:
689 case BO_LOr:
690 return extract_condition(expr);
691 default:
692 unsupported(expr);
693 return NULL;
696 width = ast_context.getIntWidth(expr->getType());
697 if (expr->getType()->isUnsignedIntegerType())
698 res = wrap(res, width);
699 else
700 res = signed_overflow(res, width);
702 return res;
705 /* Extract an affine expression from a negation operation.
707 __isl_give isl_pw_aff *PetScan::extract_affine(UnaryOperator *expr)
709 if (expr->getOpcode() == UO_Minus)
710 return isl_pw_aff_neg(extract_affine(expr->getSubExpr()));
711 if (expr->getOpcode() == UO_LNot)
712 return extract_condition(expr);
714 unsupported(expr);
715 return NULL;
718 __isl_give isl_pw_aff *PetScan::extract_affine(ParenExpr *expr)
720 return extract_affine(expr->getSubExpr());
723 /* Extract an affine expression from some special function calls.
724 * In particular, we handle "min", "max", "ceild" and "floord".
725 * In case of the latter two, the second argument needs to be
726 * a (positive) integer constant.
728 __isl_give isl_pw_aff *PetScan::extract_affine(CallExpr *expr)
730 FunctionDecl *fd;
731 string name;
732 isl_pw_aff *aff1, *aff2;
734 fd = expr->getDirectCallee();
735 if (!fd) {
736 unsupported(expr);
737 return NULL;
740 name = fd->getDeclName().getAsString();
741 if (!(expr->getNumArgs() == 2 && name == "min") &&
742 !(expr->getNumArgs() == 2 && name == "max") &&
743 !(expr->getNumArgs() == 2 && name == "floord") &&
744 !(expr->getNumArgs() == 2 && name == "ceild")) {
745 unsupported(expr);
746 return NULL;
749 if (name == "min" || name == "max") {
750 aff1 = extract_affine(expr->getArg(0));
751 aff2 = extract_affine(expr->getArg(1));
753 if (name == "min")
754 aff1 = isl_pw_aff_min(aff1, aff2);
755 else
756 aff1 = isl_pw_aff_max(aff1, aff2);
757 } else if (name == "floord" || name == "ceild") {
758 isl_val *v;
759 Expr *arg2 = expr->getArg(1);
761 if (arg2->getStmtClass() != Stmt::IntegerLiteralClass) {
762 unsupported(expr);
763 return NULL;
765 aff1 = extract_affine(expr->getArg(0));
766 v = extract_int(cast<IntegerLiteral>(arg2));
767 aff1 = isl_pw_aff_scale_down_val(aff1, v);
768 if (name == "floord")
769 aff1 = isl_pw_aff_floor(aff1);
770 else
771 aff1 = isl_pw_aff_ceil(aff1);
772 } else {
773 unsupported(expr);
774 return NULL;
777 return aff1;
780 /* This method is called when we come across an access that is
781 * nested in what is supposed to be an affine expression.
782 * If nesting is allowed, we return a new parameter that corresponds
783 * to this nested access. Otherwise, we simply complain.
785 * Note that we currently don't allow nested accesses themselves
786 * to contain any nested accesses, so we check if we can extract
787 * the access without any nesting and complain if we can't.
789 * The new parameter is resolved in resolve_nested.
791 isl_pw_aff *PetScan::nested_access(Expr *expr)
793 isl_id *id;
794 isl_space *dim;
795 isl_aff *aff;
796 isl_set *dom;
797 isl_multi_pw_aff *index;
799 if (!nesting_enabled) {
800 unsupported(expr);
801 return NULL;
804 allow_nested = false;
805 index = extract_index(expr);
806 allow_nested = true;
807 if (!index) {
808 unsupported(expr);
809 return NULL;
811 isl_multi_pw_aff_free(index);
813 id = isl_id_alloc(ctx, NULL, expr);
814 dim = isl_space_params_alloc(ctx, 1);
816 dim = isl_space_set_dim_id(dim, isl_dim_param, 0, id);
818 dom = isl_set_universe(isl_space_copy(dim));
819 aff = isl_aff_zero_on_domain(isl_local_space_from_space(dim));
820 aff = isl_aff_add_coefficient_si(aff, isl_dim_param, 0, 1);
822 return isl_pw_aff_alloc(dom, aff);
825 /* Affine expressions are not supposed to contain array accesses,
826 * but if nesting is allowed, we return a parameter corresponding
827 * to the array access.
829 __isl_give isl_pw_aff *PetScan::extract_affine(ArraySubscriptExpr *expr)
831 return nested_access(expr);
834 /* Affine expressions are not supposed to contain member accesses,
835 * but if nesting is allowed, we return a parameter corresponding
836 * to the member access.
838 __isl_give isl_pw_aff *PetScan::extract_affine(MemberExpr *expr)
840 return nested_access(expr);
843 /* Extract an affine expression from a conditional operation.
845 __isl_give isl_pw_aff *PetScan::extract_affine(ConditionalOperator *expr)
847 isl_pw_aff *cond, *lhs, *rhs;
849 cond = extract_condition(expr->getCond());
850 lhs = extract_affine(expr->getTrueExpr());
851 rhs = extract_affine(expr->getFalseExpr());
853 return isl_pw_aff_cond(cond, lhs, rhs);
856 /* Extract an affine expression, if possible, from "expr".
857 * Otherwise return NULL.
859 __isl_give isl_pw_aff *PetScan::extract_affine(Expr *expr)
861 switch (expr->getStmtClass()) {
862 case Stmt::ImplicitCastExprClass:
863 return extract_affine(cast<ImplicitCastExpr>(expr));
864 case Stmt::IntegerLiteralClass:
865 return extract_affine(cast<IntegerLiteral>(expr));
866 case Stmt::DeclRefExprClass:
867 return extract_affine(cast<DeclRefExpr>(expr));
868 case Stmt::BinaryOperatorClass:
869 return extract_affine(cast<BinaryOperator>(expr));
870 case Stmt::UnaryOperatorClass:
871 return extract_affine(cast<UnaryOperator>(expr));
872 case Stmt::ParenExprClass:
873 return extract_affine(cast<ParenExpr>(expr));
874 case Stmt::CallExprClass:
875 return extract_affine(cast<CallExpr>(expr));
876 case Stmt::ArraySubscriptExprClass:
877 return extract_affine(cast<ArraySubscriptExpr>(expr));
878 case Stmt::MemberExprClass:
879 return extract_affine(cast<MemberExpr>(expr));
880 case Stmt::ConditionalOperatorClass:
881 return extract_affine(cast<ConditionalOperator>(expr));
882 default:
883 unsupported(expr);
885 return NULL;
888 __isl_give isl_multi_pw_aff *PetScan::extract_index(ImplicitCastExpr *expr)
890 return extract_index(expr->getSubExpr());
893 /* Return the depth of an array of the given type.
895 static int array_depth(const Type *type)
897 if (type->isPointerType())
898 return 1 + array_depth(type->getPointeeType().getTypePtr());
899 if (type->isArrayType()) {
900 const ArrayType *atype;
901 type = type->getCanonicalTypeInternal().getTypePtr();
902 atype = cast<ArrayType>(type);
903 return 1 + array_depth(atype->getElementType().getTypePtr());
905 return 0;
908 /* Return the depth of the array accessed by the index expression "index".
909 * If "index" is an affine expression, i.e., if it does not access
910 * any array, then return 1.
911 * If "index" represent a member access, i.e., if its range is a wrapped
912 * relation, then return the sum of the depth of the array of structures
913 * and that of the member inside the structure.
915 static int extract_depth(__isl_keep isl_multi_pw_aff *index)
917 isl_id *id;
918 ValueDecl *decl;
920 if (!index)
921 return -1;
923 if (isl_multi_pw_aff_range_is_wrapping(index)) {
924 int domain_depth, range_depth;
925 isl_multi_pw_aff *domain, *range;
927 domain = isl_multi_pw_aff_copy(index);
928 domain = isl_multi_pw_aff_range_factor_domain(domain);
929 domain_depth = extract_depth(domain);
930 isl_multi_pw_aff_free(domain);
931 range = isl_multi_pw_aff_copy(index);
932 range = isl_multi_pw_aff_range_factor_range(range);
933 range_depth = extract_depth(range);
934 isl_multi_pw_aff_free(range);
936 return domain_depth + range_depth;
939 if (!isl_multi_pw_aff_has_tuple_id(index, isl_dim_out))
940 return 1;
942 id = isl_multi_pw_aff_get_tuple_id(index, isl_dim_out);
943 if (!id)
944 return -1;
945 decl = (ValueDecl *) isl_id_get_user(id);
946 isl_id_free(id);
948 return array_depth(decl->getType().getTypePtr());
951 /* Extract an index expression from a reference to a variable.
952 * If the variable has name "A", then the returned index expression
953 * is of the form
955 * { [] -> A[] }
957 __isl_give isl_multi_pw_aff *PetScan::extract_index(DeclRefExpr *expr)
959 return extract_index(expr->getDecl());
962 /* Extract an index expression from a variable.
963 * If the variable has name "A", then the returned index expression
964 * is of the form
966 * { [] -> A[] }
968 __isl_give isl_multi_pw_aff *PetScan::extract_index(ValueDecl *decl)
970 isl_id *id = isl_id_alloc(ctx, decl->getName().str().c_str(), decl);
971 isl_space *space = isl_space_alloc(ctx, 0, 0, 0);
973 space = isl_space_set_tuple_id(space, isl_dim_out, id);
975 return isl_multi_pw_aff_zero(space);
978 /* Extract an index expression from an integer contant.
979 * If the value of the constant is "v", then the returned access relation
980 * is
982 * { [] -> [v] }
984 __isl_give isl_multi_pw_aff *PetScan::extract_index(IntegerLiteral *expr)
986 isl_multi_pw_aff *mpa;
988 mpa = isl_multi_pw_aff_from_pw_aff(extract_affine(expr));
989 mpa = isl_multi_pw_aff_from_range(mpa);
990 return mpa;
993 /* Try and extract an index expression from the given Expr.
994 * Return NULL if it doesn't work out.
996 __isl_give isl_multi_pw_aff *PetScan::extract_index(Expr *expr)
998 switch (expr->getStmtClass()) {
999 case Stmt::ImplicitCastExprClass:
1000 return extract_index(cast<ImplicitCastExpr>(expr));
1001 case Stmt::DeclRefExprClass:
1002 return extract_index(cast<DeclRefExpr>(expr));
1003 case Stmt::ArraySubscriptExprClass:
1004 return extract_index(cast<ArraySubscriptExpr>(expr));
1005 case Stmt::IntegerLiteralClass:
1006 return extract_index(cast<IntegerLiteral>(expr));
1007 case Stmt::MemberExprClass:
1008 return extract_index(cast<MemberExpr>(expr));
1009 default:
1010 unsupported(expr);
1012 return NULL;
1015 /* Given a partial index expression "base" and an extra index "index",
1016 * append the extra index to "base" and return the result.
1017 * Additionally, add the constraints that the extra index is non-negative.
1018 * If "index" represent a member access, i.e., if its range is a wrapped
1019 * relation, then we recursively extend the range of this nested relation.
1021 static __isl_give isl_multi_pw_aff *subscript(__isl_take isl_multi_pw_aff *base,
1022 __isl_take isl_pw_aff *index)
1024 isl_id *id;
1025 isl_set *domain;
1026 isl_multi_pw_aff *access;
1027 int member_access;
1029 member_access = isl_multi_pw_aff_range_is_wrapping(base);
1030 if (member_access < 0)
1031 goto error;
1032 if (member_access) {
1033 isl_multi_pw_aff *domain, *range;
1034 isl_id *id;
1036 id = isl_multi_pw_aff_get_tuple_id(base, isl_dim_out);
1037 domain = isl_multi_pw_aff_copy(base);
1038 domain = isl_multi_pw_aff_range_factor_domain(domain);
1039 range = isl_multi_pw_aff_range_factor_range(base);
1040 range = subscript(range, index);
1041 access = isl_multi_pw_aff_range_product(domain, range);
1042 access = isl_multi_pw_aff_set_tuple_id(access, isl_dim_out, id);
1043 return access;
1046 id = isl_multi_pw_aff_get_tuple_id(base, isl_dim_set);
1047 index = isl_pw_aff_from_range(index);
1048 domain = isl_pw_aff_nonneg_set(isl_pw_aff_copy(index));
1049 index = isl_pw_aff_intersect_domain(index, domain);
1050 access = isl_multi_pw_aff_from_pw_aff(index);
1051 access = isl_multi_pw_aff_flat_range_product(base, access);
1052 access = isl_multi_pw_aff_set_tuple_id(access, isl_dim_set, id);
1054 return access;
1055 error:
1056 isl_multi_pw_aff_free(base);
1057 isl_pw_aff_free(index);
1058 return NULL;
1061 /* Extract an index expression from the given array subscript expression.
1062 * If nesting is allowed in general, then we turn it on while
1063 * examining the index expression.
1065 * We first extract an index expression from the base.
1066 * This will result in an index expression with a range that corresponds
1067 * to the earlier indices.
1068 * We then extract the current index, restrict its domain
1069 * to those values that result in a non-negative index and
1070 * append the index to the base index expression.
1072 __isl_give isl_multi_pw_aff *PetScan::extract_index(ArraySubscriptExpr *expr)
1074 Expr *base = expr->getBase();
1075 Expr *idx = expr->getIdx();
1076 isl_pw_aff *index;
1077 isl_multi_pw_aff *base_access;
1078 isl_multi_pw_aff *access;
1079 bool save_nesting = nesting_enabled;
1081 nesting_enabled = allow_nested;
1083 base_access = extract_index(base);
1084 index = extract_affine(idx);
1086 nesting_enabled = save_nesting;
1088 access = subscript(base_access, index);
1090 return access;
1093 /* Construct a name for a member access by concatenating the name
1094 * of the array of structures and the member, separated by an underscore.
1096 * The caller is responsible for freeing the result.
1098 static char *member_access_name(isl_ctx *ctx, const char *base,
1099 const char *field)
1101 int len;
1102 char *name;
1104 len = strlen(base) + 1 + strlen(field);
1105 name = isl_alloc_array(ctx, char, len + 1);
1106 if (!name)
1107 return NULL;
1108 snprintf(name, len + 1, "%s_%s", base, field);
1110 return name;
1113 /* Given an index expression "base" for an element of an array of structures
1114 * and an expression "field" for the field member being accessed, construct
1115 * an index expression for an access to that member of the given structure.
1116 * In particular, take the range product of "base" and "field" and
1117 * attach a name to the result.
1119 static __isl_give isl_multi_pw_aff *member(__isl_take isl_multi_pw_aff *base,
1120 __isl_take isl_multi_pw_aff *field)
1122 isl_ctx *ctx;
1123 isl_multi_pw_aff *access;
1124 const char *base_name, *field_name;
1125 char *name;
1127 ctx = isl_multi_pw_aff_get_ctx(base);
1129 base_name = isl_multi_pw_aff_get_tuple_name(base, isl_dim_out);
1130 field_name = isl_multi_pw_aff_get_tuple_name(field, isl_dim_out);
1131 name = member_access_name(ctx, base_name, field_name);
1133 access = isl_multi_pw_aff_range_product(base, field);
1135 access = isl_multi_pw_aff_set_tuple_name(access, isl_dim_out, name);
1136 free(name);
1138 return access;
1141 /* Extract an index expression from a member expression.
1143 * If the base access (to the structure containing the member)
1144 * is of the form
1146 * [] -> A[..]
1148 * and the member is called "f", then the member access is of
1149 * the form
1151 * [] -> A_f[A[..] -> f[]]
1153 * If the member access is to an anonymous struct, then simply return
1155 * [] -> A[..]
1157 * If the member access in the source code is of the form
1159 * A->f
1161 * then it is treated as
1163 * A[0].f
1165 __isl_give isl_multi_pw_aff *PetScan::extract_index(MemberExpr *expr)
1167 Expr *base = expr->getBase();
1168 FieldDecl *field = cast<FieldDecl>(expr->getMemberDecl());
1169 isl_multi_pw_aff *base_access, *field_access;
1170 isl_id *id;
1171 isl_space *space;
1173 base_access = extract_index(base);
1175 if (expr->isArrow()) {
1176 isl_space *space = isl_space_params_alloc(ctx, 0);
1177 isl_local_space *ls = isl_local_space_from_space(space);
1178 isl_aff *aff = isl_aff_zero_on_domain(ls);
1179 isl_pw_aff *index = isl_pw_aff_from_aff(aff);
1180 base_access = subscript(base_access, index);
1183 if (field->isAnonymousStructOrUnion())
1184 return base_access;
1186 id = isl_id_alloc(ctx, field->getName().str().c_str(), field);
1187 space = isl_multi_pw_aff_get_domain_space(base_access);
1188 space = isl_space_from_domain(space);
1189 space = isl_space_set_tuple_id(space, isl_dim_out, id);
1190 field_access = isl_multi_pw_aff_zero(space);
1192 return member(base_access, field_access);
1195 /* Check if "expr" calls function "minmax" with two arguments and if so
1196 * make lhs and rhs refer to these two arguments.
1198 static bool is_minmax(Expr *expr, const char *minmax, Expr *&lhs, Expr *&rhs)
1200 CallExpr *call;
1201 FunctionDecl *fd;
1202 string name;
1204 if (expr->getStmtClass() != Stmt::CallExprClass)
1205 return false;
1207 call = cast<CallExpr>(expr);
1208 fd = call->getDirectCallee();
1209 if (!fd)
1210 return false;
1212 if (call->getNumArgs() != 2)
1213 return false;
1215 name = fd->getDeclName().getAsString();
1216 if (name != minmax)
1217 return false;
1219 lhs = call->getArg(0);
1220 rhs = call->getArg(1);
1222 return true;
1225 /* Check if "expr" is of the form min(lhs, rhs) and if so make
1226 * lhs and rhs refer to the two arguments.
1228 static bool is_min(Expr *expr, Expr *&lhs, Expr *&rhs)
1230 return is_minmax(expr, "min", lhs, rhs);
1233 /* Check if "expr" is of the form max(lhs, rhs) and if so make
1234 * lhs and rhs refer to the two arguments.
1236 static bool is_max(Expr *expr, Expr *&lhs, Expr *&rhs)
1238 return is_minmax(expr, "max", lhs, rhs);
1241 /* Return "lhs && rhs", defined on the shared definition domain.
1243 static __isl_give isl_pw_aff *pw_aff_and(__isl_take isl_pw_aff *lhs,
1244 __isl_take isl_pw_aff *rhs)
1246 isl_set *cond;
1247 isl_set *dom;
1249 dom = isl_set_intersect(isl_pw_aff_domain(isl_pw_aff_copy(lhs)),
1250 isl_pw_aff_domain(isl_pw_aff_copy(rhs)));
1251 cond = isl_set_intersect(isl_pw_aff_non_zero_set(lhs),
1252 isl_pw_aff_non_zero_set(rhs));
1253 return indicator_function(cond, dom);
1256 /* Return "lhs && rhs", with shortcut semantics.
1257 * That is, if lhs is false, then the result is defined even if rhs is not.
1258 * In practice, we compute lhs ? rhs : lhs.
1260 static __isl_give isl_pw_aff *pw_aff_and_then(__isl_take isl_pw_aff *lhs,
1261 __isl_take isl_pw_aff *rhs)
1263 return isl_pw_aff_cond(isl_pw_aff_copy(lhs), rhs, lhs);
1266 /* Return "lhs || rhs", with shortcut semantics.
1267 * That is, if lhs is true, then the result is defined even if rhs is not.
1268 * In practice, we compute lhs ? lhs : rhs.
1270 static __isl_give isl_pw_aff *pw_aff_or_else(__isl_take isl_pw_aff *lhs,
1271 __isl_take isl_pw_aff *rhs)
1273 return isl_pw_aff_cond(isl_pw_aff_copy(lhs), lhs, rhs);
1276 /* Extract an affine expressions representing the comparison "LHS op RHS"
1277 * "comp" is the original statement that "LHS op RHS" is derived from
1278 * and is used for diagnostics.
1280 * If the comparison is of the form
1282 * a <= min(b,c)
1284 * then the expression is constructed as the conjunction of
1285 * the comparisons
1287 * a <= b and a <= c
1289 * A similar optimization is performed for max(a,b) <= c.
1290 * We do this because that will lead to simpler representations
1291 * of the expression.
1292 * If isl is ever enhanced to explicitly deal with min and max expressions,
1293 * this optimization can be removed.
1295 __isl_give isl_pw_aff *PetScan::extract_comparison(BinaryOperatorKind op,
1296 Expr *LHS, Expr *RHS, Stmt *comp)
1298 isl_pw_aff *lhs;
1299 isl_pw_aff *rhs;
1300 isl_pw_aff *res;
1301 isl_set *cond;
1302 isl_set *dom;
1304 if (op == BO_GT)
1305 return extract_comparison(BO_LT, RHS, LHS, comp);
1306 if (op == BO_GE)
1307 return extract_comparison(BO_LE, RHS, LHS, comp);
1309 if (op == BO_LT || op == BO_LE) {
1310 Expr *expr1, *expr2;
1311 if (is_min(RHS, expr1, expr2)) {
1312 lhs = extract_comparison(op, LHS, expr1, comp);
1313 rhs = extract_comparison(op, LHS, expr2, comp);
1314 return pw_aff_and(lhs, rhs);
1316 if (is_max(LHS, expr1, expr2)) {
1317 lhs = extract_comparison(op, expr1, RHS, comp);
1318 rhs = extract_comparison(op, expr2, RHS, comp);
1319 return pw_aff_and(lhs, rhs);
1323 lhs = extract_affine(LHS);
1324 rhs = extract_affine(RHS);
1326 dom = isl_pw_aff_domain(isl_pw_aff_copy(lhs));
1327 dom = isl_set_intersect(dom, isl_pw_aff_domain(isl_pw_aff_copy(rhs)));
1329 switch (op) {
1330 case BO_LT:
1331 cond = isl_pw_aff_lt_set(lhs, rhs);
1332 break;
1333 case BO_LE:
1334 cond = isl_pw_aff_le_set(lhs, rhs);
1335 break;
1336 case BO_EQ:
1337 cond = isl_pw_aff_eq_set(lhs, rhs);
1338 break;
1339 case BO_NE:
1340 cond = isl_pw_aff_ne_set(lhs, rhs);
1341 break;
1342 default:
1343 isl_pw_aff_free(lhs);
1344 isl_pw_aff_free(rhs);
1345 isl_set_free(dom);
1346 unsupported(comp);
1347 return NULL;
1350 cond = isl_set_coalesce(cond);
1351 res = indicator_function(cond, dom);
1353 return res;
1356 __isl_give isl_pw_aff *PetScan::extract_comparison(BinaryOperator *comp)
1358 return extract_comparison(comp->getOpcode(), comp->getLHS(),
1359 comp->getRHS(), comp);
1362 /* Extract an affine expression representing the negation (logical not)
1363 * of a subexpression.
1365 __isl_give isl_pw_aff *PetScan::extract_boolean(UnaryOperator *op)
1367 isl_set *set_cond, *dom;
1368 isl_pw_aff *cond, *res;
1370 cond = extract_condition(op->getSubExpr());
1372 dom = isl_pw_aff_domain(isl_pw_aff_copy(cond));
1374 set_cond = isl_pw_aff_zero_set(cond);
1376 res = indicator_function(set_cond, dom);
1378 return res;
1381 /* Extract an affine expression representing the disjunction (logical or)
1382 * or conjunction (logical and) of two subexpressions.
1384 __isl_give isl_pw_aff *PetScan::extract_boolean(BinaryOperator *comp)
1386 isl_pw_aff *lhs, *rhs;
1388 lhs = extract_condition(comp->getLHS());
1389 rhs = extract_condition(comp->getRHS());
1391 switch (comp->getOpcode()) {
1392 case BO_LAnd:
1393 return pw_aff_and_then(lhs, rhs);
1394 case BO_LOr:
1395 return pw_aff_or_else(lhs, rhs);
1396 default:
1397 isl_pw_aff_free(lhs);
1398 isl_pw_aff_free(rhs);
1401 unsupported(comp);
1402 return NULL;
1405 __isl_give isl_pw_aff *PetScan::extract_condition(UnaryOperator *expr)
1407 switch (expr->getOpcode()) {
1408 case UO_LNot:
1409 return extract_boolean(expr);
1410 default:
1411 unsupported(expr);
1412 return NULL;
1416 /* Extract the affine expression "expr != 0 ? 1 : 0".
1418 __isl_give isl_pw_aff *PetScan::extract_implicit_condition(Expr *expr)
1420 isl_pw_aff *res;
1421 isl_set *set, *dom;
1423 res = extract_affine(expr);
1425 dom = isl_pw_aff_domain(isl_pw_aff_copy(res));
1426 set = isl_pw_aff_non_zero_set(res);
1428 res = indicator_function(set, dom);
1430 return res;
1433 /* Extract an affine expression from a boolean expression.
1434 * In particular, return the expression "expr ? 1 : 0".
1436 * If the expression doesn't look like a condition, we assume it
1437 * is an affine expression and return the condition "expr != 0 ? 1 : 0".
1439 __isl_give isl_pw_aff *PetScan::extract_condition(Expr *expr)
1441 BinaryOperator *comp;
1443 if (!expr) {
1444 isl_set *u = isl_set_universe(isl_space_params_alloc(ctx, 0));
1445 return indicator_function(u, isl_set_copy(u));
1448 if (expr->getStmtClass() == Stmt::ParenExprClass)
1449 return extract_condition(cast<ParenExpr>(expr)->getSubExpr());
1451 if (expr->getStmtClass() == Stmt::UnaryOperatorClass)
1452 return extract_condition(cast<UnaryOperator>(expr));
1454 if (expr->getStmtClass() != Stmt::BinaryOperatorClass)
1455 return extract_implicit_condition(expr);
1457 comp = cast<BinaryOperator>(expr);
1458 switch (comp->getOpcode()) {
1459 case BO_LT:
1460 case BO_LE:
1461 case BO_GT:
1462 case BO_GE:
1463 case BO_EQ:
1464 case BO_NE:
1465 return extract_comparison(comp);
1466 case BO_LAnd:
1467 case BO_LOr:
1468 return extract_boolean(comp);
1469 default:
1470 return extract_implicit_condition(expr);
1474 static enum pet_op_type UnaryOperatorKind2pet_op_type(UnaryOperatorKind kind)
1476 switch (kind) {
1477 case UO_Minus:
1478 return pet_op_minus;
1479 case UO_Not:
1480 return pet_op_not;
1481 case UO_PostInc:
1482 return pet_op_post_inc;
1483 case UO_PostDec:
1484 return pet_op_post_dec;
1485 case UO_PreInc:
1486 return pet_op_pre_inc;
1487 case UO_PreDec:
1488 return pet_op_pre_dec;
1489 default:
1490 return pet_op_last;
1494 static enum pet_op_type BinaryOperatorKind2pet_op_type(BinaryOperatorKind kind)
1496 switch (kind) {
1497 case BO_AddAssign:
1498 return pet_op_add_assign;
1499 case BO_SubAssign:
1500 return pet_op_sub_assign;
1501 case BO_MulAssign:
1502 return pet_op_mul_assign;
1503 case BO_DivAssign:
1504 return pet_op_div_assign;
1505 case BO_Assign:
1506 return pet_op_assign;
1507 case BO_Add:
1508 return pet_op_add;
1509 case BO_Sub:
1510 return pet_op_sub;
1511 case BO_Mul:
1512 return pet_op_mul;
1513 case BO_Div:
1514 return pet_op_div;
1515 case BO_Rem:
1516 return pet_op_mod;
1517 case BO_Shl:
1518 return pet_op_shl;
1519 case BO_Shr:
1520 return pet_op_shr;
1521 case BO_EQ:
1522 return pet_op_eq;
1523 case BO_NE:
1524 return pet_op_ne;
1525 case BO_LE:
1526 return pet_op_le;
1527 case BO_GE:
1528 return pet_op_ge;
1529 case BO_LT:
1530 return pet_op_lt;
1531 case BO_GT:
1532 return pet_op_gt;
1533 case BO_And:
1534 return pet_op_and;
1535 case BO_Xor:
1536 return pet_op_xor;
1537 case BO_Or:
1538 return pet_op_or;
1539 default:
1540 return pet_op_last;
1544 /* Construct a pet_expr representing a unary operator expression.
1546 struct pet_expr *PetScan::extract_expr(UnaryOperator *expr)
1548 struct pet_expr *arg;
1549 enum pet_op_type op;
1551 op = UnaryOperatorKind2pet_op_type(expr->getOpcode());
1552 if (op == pet_op_last) {
1553 unsupported(expr);
1554 return NULL;
1557 arg = extract_expr(expr->getSubExpr());
1559 if (expr->isIncrementDecrementOp() &&
1560 arg && arg->type == pet_expr_access) {
1561 mark_write(arg);
1562 arg->acc.read = 1;
1565 return pet_expr_new_unary(ctx, op, arg);
1568 /* Mark the given access pet_expr as a write.
1569 * If a scalar is being accessed, then mark its value
1570 * as unknown in assigned_value.
1572 void PetScan::mark_write(struct pet_expr *access)
1574 isl_id *id;
1575 ValueDecl *decl;
1577 if (!access)
1578 return;
1580 access->acc.write = 1;
1581 access->acc.read = 0;
1583 if (!pet_expr_is_scalar_access(access))
1584 return;
1586 id = pet_expr_access_get_id(access);
1587 decl = (ValueDecl *) isl_id_get_user(id);
1588 clear_assignment(assigned_value, decl);
1589 isl_id_free(id);
1592 /* Assign "rhs" to "lhs".
1594 * In particular, if "lhs" is a scalar variable, then mark
1595 * the variable as having been assigned. If, furthermore, "rhs"
1596 * is an affine expression, then keep track of this value in assigned_value
1597 * so that we can plug it in when we later come across the same variable.
1599 void PetScan::assign(struct pet_expr *lhs, Expr *rhs)
1601 isl_id *id;
1602 ValueDecl *decl;
1603 isl_pw_aff *pa;
1605 if (!lhs)
1606 return;
1607 if (!pet_expr_is_scalar_access(lhs))
1608 return;
1610 id = pet_expr_access_get_id(lhs);
1611 decl = (ValueDecl *) isl_id_get_user(id);
1612 isl_id_free(id);
1614 pa = try_extract_affine(rhs);
1615 clear_assignment(assigned_value, decl);
1616 if (!pa)
1617 return;
1618 assigned_value[decl] = pa;
1619 insert_expression(pa);
1622 /* Construct a pet_expr representing a binary operator expression.
1624 * If the top level operator is an assignment and the LHS is an access,
1625 * then we mark that access as a write. If the operator is a compound
1626 * assignment, the access is marked as both a read and a write.
1628 * If "expr" assigns something to a scalar variable, then we mark
1629 * the variable as having been assigned. If, furthermore, the expression
1630 * is affine, then keep track of this value in assigned_value
1631 * so that we can plug it in when we later come across the same variable.
1633 struct pet_expr *PetScan::extract_expr(BinaryOperator *expr)
1635 struct pet_expr *lhs, *rhs;
1636 enum pet_op_type op;
1638 op = BinaryOperatorKind2pet_op_type(expr->getOpcode());
1639 if (op == pet_op_last) {
1640 unsupported(expr);
1641 return NULL;
1644 lhs = extract_expr(expr->getLHS());
1645 rhs = extract_expr(expr->getRHS());
1647 if (expr->isAssignmentOp() && lhs && lhs->type == pet_expr_access) {
1648 mark_write(lhs);
1649 if (expr->isCompoundAssignmentOp())
1650 lhs->acc.read = 1;
1653 if (expr->getOpcode() == BO_Assign)
1654 assign(lhs, expr->getRHS());
1656 return pet_expr_new_binary(ctx, op, lhs, rhs);
1659 /* Construct a pet_scop with a single statement killing the entire
1660 * array "array".
1662 struct pet_scop *PetScan::kill(Stmt *stmt, struct pet_array *array)
1664 isl_id *id;
1665 isl_space *space;
1666 isl_multi_pw_aff *index;
1667 isl_map *access;
1668 struct pet_expr *expr;
1670 if (!array)
1671 return NULL;
1672 access = isl_map_from_range(isl_set_copy(array->extent));
1673 id = isl_set_get_tuple_id(array->extent);
1674 space = isl_space_alloc(ctx, 0, 0, 0);
1675 space = isl_space_set_tuple_id(space, isl_dim_out, id);
1676 index = isl_multi_pw_aff_zero(space);
1677 expr = pet_expr_kill_from_access_and_index(access, index);
1678 return extract(stmt, expr);
1681 /* Construct a pet_scop for a (single) variable declaration.
1683 * The scop contains the variable being declared (as an array)
1684 * and a statement killing the array.
1686 * If the variable is initialized in the AST, then the scop
1687 * also contains an assignment to the variable.
1689 struct pet_scop *PetScan::extract(DeclStmt *stmt)
1691 Decl *decl;
1692 VarDecl *vd;
1693 struct pet_expr *lhs, *rhs, *pe;
1694 struct pet_scop *scop_decl, *scop;
1695 struct pet_array *array;
1697 if (!stmt->isSingleDecl()) {
1698 unsupported(stmt);
1699 return NULL;
1702 decl = stmt->getSingleDecl();
1703 vd = cast<VarDecl>(decl);
1705 array = extract_array(ctx, vd, NULL);
1706 if (array)
1707 array->declared = 1;
1708 scop_decl = kill(stmt, array);
1709 scop_decl = pet_scop_add_array(scop_decl, array);
1711 if (!vd->getInit())
1712 return scop_decl;
1714 lhs = extract_access_expr(vd);
1715 rhs = extract_expr(vd->getInit());
1717 mark_write(lhs);
1718 assign(lhs, vd->getInit());
1720 pe = pet_expr_new_binary(ctx, pet_op_assign, lhs, rhs);
1721 scop = extract(stmt, pe);
1723 scop_decl = pet_scop_prefix(scop_decl, 0);
1724 scop = pet_scop_prefix(scop, 1);
1726 scop = pet_scop_add_seq(ctx, scop_decl, scop);
1728 return scop;
1731 /* Construct a pet_expr representing a conditional operation.
1733 * We first try to extract the condition as an affine expression.
1734 * If that fails, we construct a pet_expr tree representing the condition.
1736 struct pet_expr *PetScan::extract_expr(ConditionalOperator *expr)
1738 struct pet_expr *cond, *lhs, *rhs;
1739 isl_pw_aff *pa;
1741 pa = try_extract_affine(expr->getCond());
1742 if (pa) {
1743 isl_multi_pw_aff *test = isl_multi_pw_aff_from_pw_aff(pa);
1744 test = isl_multi_pw_aff_from_range(test);
1745 cond = pet_expr_from_index(test);
1746 } else
1747 cond = extract_expr(expr->getCond());
1748 lhs = extract_expr(expr->getTrueExpr());
1749 rhs = extract_expr(expr->getFalseExpr());
1751 return pet_expr_new_ternary(ctx, cond, lhs, rhs);
1754 struct pet_expr *PetScan::extract_expr(ImplicitCastExpr *expr)
1756 return extract_expr(expr->getSubExpr());
1759 /* Construct a pet_expr representing a floating point value.
1761 * If the floating point literal does not appear in a macro,
1762 * then we use the original representation in the source code
1763 * as the string representation. Otherwise, we use the pretty
1764 * printer to produce a string representation.
1766 struct pet_expr *PetScan::extract_expr(FloatingLiteral *expr)
1768 double d;
1769 string s;
1770 const LangOptions &LO = PP.getLangOpts();
1771 SourceLocation loc = expr->getLocation();
1773 if (!loc.isMacroID()) {
1774 SourceManager &SM = PP.getSourceManager();
1775 unsigned len = Lexer::MeasureTokenLength(loc, SM, LO);
1776 s = string(SM.getCharacterData(loc), len);
1777 } else {
1778 llvm::raw_string_ostream S(s);
1779 expr->printPretty(S, 0, PrintingPolicy(LO));
1780 S.str();
1782 d = expr->getValueAsApproximateDouble();
1783 return pet_expr_new_double(ctx, d, s.c_str());
1786 /* Extract an index expression from "expr" and then convert it into
1787 * an access pet_expr.
1789 struct pet_expr *PetScan::extract_access_expr(Expr *expr)
1791 isl_multi_pw_aff *index;
1792 struct pet_expr *pe;
1793 int depth;
1795 index = extract_index(expr);
1796 depth = extract_depth(index);
1798 pe = pet_expr_from_index_and_depth(index, depth);
1800 return pe;
1803 /* Extract an index expression from "decl" and then convert it into
1804 * an access pet_expr.
1806 struct pet_expr *PetScan::extract_access_expr(ValueDecl *decl)
1808 isl_multi_pw_aff *index;
1809 struct pet_expr *pe;
1810 int depth;
1812 index = extract_index(decl);
1813 depth = extract_depth(index);
1815 pe = pet_expr_from_index_and_depth(index, depth);
1817 return pe;
1820 struct pet_expr *PetScan::extract_expr(ParenExpr *expr)
1822 return extract_expr(expr->getSubExpr());
1825 /* Extract an assume statement from the argument "expr"
1826 * of a __pencil_assume statement.
1828 struct pet_expr *PetScan::extract_assume(Expr *expr)
1830 isl_pw_aff *cond;
1831 struct pet_expr *res;
1833 cond = try_extract_affine_condition(expr);
1834 if (!cond) {
1835 res = extract_expr(expr);
1836 } else {
1837 isl_multi_pw_aff *index;
1838 index = isl_multi_pw_aff_from_pw_aff(cond);
1839 index = isl_multi_pw_aff_from_range(index);
1840 res = pet_expr_from_index(index);
1842 return pet_expr_new_unary(ctx, pet_op_assume, res);
1845 /* Construct a pet_expr corresponding to the function call argument "expr".
1846 * The argument appears in position "pos" of a call to function "fd".
1848 * If we are passing along a pointer to an array element
1849 * or an entire row or even higher dimensional slice of an array,
1850 * then the function being called may write into the array.
1852 * We assume here that if the function is declared to take a pointer
1853 * to a const type, then the function will perform a read
1854 * and that otherwise, it will perform a write.
1856 struct pet_expr *PetScan::extract_argument(FunctionDecl *fd, int pos,
1857 Expr *expr)
1859 struct pet_expr *res;
1860 int is_addr = 0;
1861 pet_expr *main_arg;
1862 Stmt::StmtClass sc;
1864 if (expr->getStmtClass() == Stmt::ImplicitCastExprClass) {
1865 ImplicitCastExpr *ice = cast<ImplicitCastExpr>(expr);
1866 expr = ice->getSubExpr();
1868 if (expr->getStmtClass() == Stmt::UnaryOperatorClass) {
1869 UnaryOperator *op = cast<UnaryOperator>(expr);
1870 if (op->getOpcode() == UO_AddrOf) {
1871 is_addr = 1;
1872 expr = op->getSubExpr();
1875 res = extract_expr(expr);
1876 main_arg = res;
1877 if (is_addr)
1878 res = pet_expr_new_unary(ctx, pet_op_address_of, res);
1879 if (!res)
1880 return NULL;
1881 sc = expr->getStmtClass();
1882 if ((sc == Stmt::ArraySubscriptExprClass ||
1883 sc == Stmt::MemberExprClass) &&
1884 array_depth(expr->getType().getTypePtr()) > 0)
1885 is_addr = 1;
1886 if (is_addr && main_arg->type == pet_expr_access) {
1887 ParmVarDecl *parm;
1888 if (!fd->hasPrototype()) {
1889 report_prototype_required(expr);
1890 return pet_expr_free(res);
1892 parm = fd->getParamDecl(pos);
1893 if (!const_base(parm->getType()))
1894 mark_write(main_arg);
1897 return res;
1900 /* Construct a pet_expr representing a function call.
1902 * In the special case of a "call" to __pencil_assume,
1903 * construct an assume expression instead.
1905 struct pet_expr *PetScan::extract_expr(CallExpr *expr)
1907 struct pet_expr *res = NULL;
1908 FunctionDecl *fd;
1909 string name;
1910 unsigned n_arg;
1912 fd = expr->getDirectCallee();
1913 if (!fd) {
1914 unsupported(expr);
1915 return NULL;
1918 name = fd->getDeclName().getAsString();
1919 n_arg = expr->getNumArgs();
1921 if (n_arg == 1 && name == "__pencil_assume")
1922 return extract_assume(expr->getArg(0));
1924 res = pet_expr_new_call(ctx, name.c_str(), n_arg);
1925 if (!res)
1926 return NULL;
1928 for (int i = 0; i < n_arg; ++i) {
1929 Expr *arg = expr->getArg(i);
1930 res->args[i] = PetScan::extract_argument(fd, i, arg);
1931 if (!res->args[i])
1932 goto error;
1935 return res;
1936 error:
1937 pet_expr_free(res);
1938 return NULL;
1941 /* Construct a pet_expr representing a (C style) cast.
1943 struct pet_expr *PetScan::extract_expr(CStyleCastExpr *expr)
1945 struct pet_expr *arg;
1946 QualType type;
1948 arg = extract_expr(expr->getSubExpr());
1949 if (!arg)
1950 return NULL;
1952 type = expr->getTypeAsWritten();
1953 return pet_expr_new_cast(ctx, type.getAsString().c_str(), arg);
1956 /* Try and onstruct a pet_expr representing "expr".
1958 struct pet_expr *PetScan::extract_expr(Expr *expr)
1960 switch (expr->getStmtClass()) {
1961 case Stmt::UnaryOperatorClass:
1962 return extract_expr(cast<UnaryOperator>(expr));
1963 case Stmt::CompoundAssignOperatorClass:
1964 case Stmt::BinaryOperatorClass:
1965 return extract_expr(cast<BinaryOperator>(expr));
1966 case Stmt::ImplicitCastExprClass:
1967 return extract_expr(cast<ImplicitCastExpr>(expr));
1968 case Stmt::ArraySubscriptExprClass:
1969 case Stmt::DeclRefExprClass:
1970 case Stmt::IntegerLiteralClass:
1971 case Stmt::MemberExprClass:
1972 return extract_access_expr(expr);
1973 case Stmt::FloatingLiteralClass:
1974 return extract_expr(cast<FloatingLiteral>(expr));
1975 case Stmt::ParenExprClass:
1976 return extract_expr(cast<ParenExpr>(expr));
1977 case Stmt::ConditionalOperatorClass:
1978 return extract_expr(cast<ConditionalOperator>(expr));
1979 case Stmt::CallExprClass:
1980 return extract_expr(cast<CallExpr>(expr));
1981 case Stmt::CStyleCastExprClass:
1982 return extract_expr(cast<CStyleCastExpr>(expr));
1983 default:
1984 unsupported(expr);
1986 return NULL;
1989 /* Check if the given initialization statement is an assignment.
1990 * If so, return that assignment. Otherwise return NULL.
1992 BinaryOperator *PetScan::initialization_assignment(Stmt *init)
1994 BinaryOperator *ass;
1996 if (init->getStmtClass() != Stmt::BinaryOperatorClass)
1997 return NULL;
1999 ass = cast<BinaryOperator>(init);
2000 if (ass->getOpcode() != BO_Assign)
2001 return NULL;
2003 return ass;
2006 /* Check if the given initialization statement is a declaration
2007 * of a single variable.
2008 * If so, return that declaration. Otherwise return NULL.
2010 Decl *PetScan::initialization_declaration(Stmt *init)
2012 DeclStmt *decl;
2014 if (init->getStmtClass() != Stmt::DeclStmtClass)
2015 return NULL;
2017 decl = cast<DeclStmt>(init);
2019 if (!decl->isSingleDecl())
2020 return NULL;
2022 return decl->getSingleDecl();
2025 /* Given the assignment operator in the initialization of a for loop,
2026 * extract the induction variable, i.e., the (integer)variable being
2027 * assigned.
2029 ValueDecl *PetScan::extract_induction_variable(BinaryOperator *init)
2031 Expr *lhs;
2032 DeclRefExpr *ref;
2033 ValueDecl *decl;
2034 const Type *type;
2036 lhs = init->getLHS();
2037 if (lhs->getStmtClass() != Stmt::DeclRefExprClass) {
2038 unsupported(init);
2039 return NULL;
2042 ref = cast<DeclRefExpr>(lhs);
2043 decl = ref->getDecl();
2044 type = decl->getType().getTypePtr();
2046 if (!type->isIntegerType()) {
2047 unsupported(lhs);
2048 return NULL;
2051 return decl;
2054 /* Given the initialization statement of a for loop and the single
2055 * declaration in this initialization statement,
2056 * extract the induction variable, i.e., the (integer) variable being
2057 * declared.
2059 VarDecl *PetScan::extract_induction_variable(Stmt *init, Decl *decl)
2061 VarDecl *vd;
2063 vd = cast<VarDecl>(decl);
2065 const QualType type = vd->getType();
2066 if (!type->isIntegerType()) {
2067 unsupported(init);
2068 return NULL;
2071 if (!vd->getInit()) {
2072 unsupported(init);
2073 return NULL;
2076 return vd;
2079 /* Check that op is of the form iv++ or iv--.
2080 * Return an affine expression "1" or "-1" accordingly.
2082 __isl_give isl_pw_aff *PetScan::extract_unary_increment(
2083 clang::UnaryOperator *op, clang::ValueDecl *iv)
2085 Expr *sub;
2086 DeclRefExpr *ref;
2087 isl_space *space;
2088 isl_aff *aff;
2090 if (!op->isIncrementDecrementOp()) {
2091 unsupported(op);
2092 return NULL;
2095 sub = op->getSubExpr();
2096 if (sub->getStmtClass() != Stmt::DeclRefExprClass) {
2097 unsupported(op);
2098 return NULL;
2101 ref = cast<DeclRefExpr>(sub);
2102 if (ref->getDecl() != iv) {
2103 unsupported(op);
2104 return NULL;
2107 space = isl_space_params_alloc(ctx, 0);
2108 aff = isl_aff_zero_on_domain(isl_local_space_from_space(space));
2110 if (op->isIncrementOp())
2111 aff = isl_aff_add_constant_si(aff, 1);
2112 else
2113 aff = isl_aff_add_constant_si(aff, -1);
2115 return isl_pw_aff_from_aff(aff);
2118 /* If the isl_pw_aff on which isl_pw_aff_foreach_piece is called
2119 * has a single constant expression, then put this constant in *user.
2120 * The caller is assumed to have checked that this function will
2121 * be called exactly once.
2123 static int extract_cst(__isl_take isl_set *set, __isl_take isl_aff *aff,
2124 void *user)
2126 isl_val **inc = (isl_val **)user;
2127 int res = 0;
2129 if (isl_aff_is_cst(aff))
2130 *inc = isl_aff_get_constant_val(aff);
2131 else
2132 res = -1;
2134 isl_set_free(set);
2135 isl_aff_free(aff);
2137 return res;
2140 /* Check if op is of the form
2142 * iv = iv + inc
2144 * and return inc as an affine expression.
2146 * We extract an affine expression from the RHS, subtract iv and return
2147 * the result.
2149 __isl_give isl_pw_aff *PetScan::extract_binary_increment(BinaryOperator *op,
2150 clang::ValueDecl *iv)
2152 Expr *lhs;
2153 DeclRefExpr *ref;
2154 isl_id *id;
2155 isl_space *dim;
2156 isl_aff *aff;
2157 isl_pw_aff *val;
2159 if (op->getOpcode() != BO_Assign) {
2160 unsupported(op);
2161 return NULL;
2164 lhs = op->getLHS();
2165 if (lhs->getStmtClass() != Stmt::DeclRefExprClass) {
2166 unsupported(op);
2167 return NULL;
2170 ref = cast<DeclRefExpr>(lhs);
2171 if (ref->getDecl() != iv) {
2172 unsupported(op);
2173 return NULL;
2176 val = extract_affine(op->getRHS());
2178 id = isl_id_alloc(ctx, iv->getName().str().c_str(), iv);
2180 dim = isl_space_params_alloc(ctx, 1);
2181 dim = isl_space_set_dim_id(dim, isl_dim_param, 0, id);
2182 aff = isl_aff_zero_on_domain(isl_local_space_from_space(dim));
2183 aff = isl_aff_add_coefficient_si(aff, isl_dim_param, 0, 1);
2185 val = isl_pw_aff_sub(val, isl_pw_aff_from_aff(aff));
2187 return val;
2190 /* Check that op is of the form iv += cst or iv -= cst
2191 * and return an affine expression corresponding oto cst or -cst accordingly.
2193 __isl_give isl_pw_aff *PetScan::extract_compound_increment(
2194 CompoundAssignOperator *op, clang::ValueDecl *iv)
2196 Expr *lhs;
2197 DeclRefExpr *ref;
2198 bool neg = false;
2199 isl_pw_aff *val;
2200 BinaryOperatorKind opcode;
2202 opcode = op->getOpcode();
2203 if (opcode != BO_AddAssign && opcode != BO_SubAssign) {
2204 unsupported(op);
2205 return NULL;
2207 if (opcode == BO_SubAssign)
2208 neg = true;
2210 lhs = op->getLHS();
2211 if (lhs->getStmtClass() != Stmt::DeclRefExprClass) {
2212 unsupported(op);
2213 return NULL;
2216 ref = cast<DeclRefExpr>(lhs);
2217 if (ref->getDecl() != iv) {
2218 unsupported(op);
2219 return NULL;
2222 val = extract_affine(op->getRHS());
2223 if (neg)
2224 val = isl_pw_aff_neg(val);
2226 return val;
2229 /* Check that the increment of the given for loop increments
2230 * (or decrements) the induction variable "iv" and return
2231 * the increment as an affine expression if successful.
2233 __isl_give isl_pw_aff *PetScan::extract_increment(clang::ForStmt *stmt,
2234 ValueDecl *iv)
2236 Stmt *inc = stmt->getInc();
2238 if (!inc) {
2239 unsupported(stmt);
2240 return NULL;
2243 if (inc->getStmtClass() == Stmt::UnaryOperatorClass)
2244 return extract_unary_increment(cast<UnaryOperator>(inc), iv);
2245 if (inc->getStmtClass() == Stmt::CompoundAssignOperatorClass)
2246 return extract_compound_increment(
2247 cast<CompoundAssignOperator>(inc), iv);
2248 if (inc->getStmtClass() == Stmt::BinaryOperatorClass)
2249 return extract_binary_increment(cast<BinaryOperator>(inc), iv);
2251 unsupported(inc);
2252 return NULL;
2255 /* Embed the given iteration domain in an extra outer loop
2256 * with induction variable "var".
2257 * If this variable appeared as a parameter in the constraints,
2258 * it is replaced by the new outermost dimension.
2260 static __isl_give isl_set *embed(__isl_take isl_set *set,
2261 __isl_take isl_id *var)
2263 int pos;
2265 set = isl_set_insert_dims(set, isl_dim_set, 0, 1);
2266 pos = isl_set_find_dim_by_id(set, isl_dim_param, var);
2267 if (pos >= 0) {
2268 set = isl_set_equate(set, isl_dim_param, pos, isl_dim_set, 0);
2269 set = isl_set_project_out(set, isl_dim_param, pos, 1);
2272 isl_id_free(var);
2273 return set;
2276 /* Return those elements in the space of "cond" that come after
2277 * (based on "sign") an element in "cond".
2279 static __isl_give isl_set *after(__isl_take isl_set *cond, int sign)
2281 isl_map *previous_to_this;
2283 if (sign > 0)
2284 previous_to_this = isl_map_lex_lt(isl_set_get_space(cond));
2285 else
2286 previous_to_this = isl_map_lex_gt(isl_set_get_space(cond));
2288 cond = isl_set_apply(cond, previous_to_this);
2290 return cond;
2293 /* Create the infinite iteration domain
2295 * { [id] : id >= 0 }
2297 * If "scop" has an affine skip of type pet_skip_later,
2298 * then remove those iterations i that have an earlier iteration
2299 * where the skip condition is satisfied, meaning that iteration i
2300 * is not executed.
2301 * Since we are dealing with a loop without loop iterator,
2302 * the skip condition cannot refer to the current loop iterator and
2303 * so effectively, the returned set is of the form
2305 * { [0]; [id] : id >= 1 and not skip }
2307 static __isl_give isl_set *infinite_domain(__isl_take isl_id *id,
2308 struct pet_scop *scop)
2310 isl_ctx *ctx = isl_id_get_ctx(id);
2311 isl_set *domain;
2312 isl_set *skip;
2314 domain = isl_set_nat_universe(isl_space_set_alloc(ctx, 0, 1));
2315 domain = isl_set_set_dim_id(domain, isl_dim_set, 0, id);
2317 if (!pet_scop_has_affine_skip(scop, pet_skip_later))
2318 return domain;
2320 skip = pet_scop_get_affine_skip_domain(scop, pet_skip_later);
2321 skip = embed(skip, isl_id_copy(id));
2322 skip = isl_set_intersect(skip , isl_set_copy(domain));
2323 domain = isl_set_subtract(domain, after(skip, 1));
2325 return domain;
2328 /* Create an identity affine expression on the space containing "domain",
2329 * which is assumed to be one-dimensional.
2331 static __isl_give isl_aff *identity_aff(__isl_keep isl_set *domain)
2333 isl_local_space *ls;
2335 ls = isl_local_space_from_space(isl_set_get_space(domain));
2336 return isl_aff_var_on_domain(ls, isl_dim_set, 0);
2339 /* Create an affine expression that maps elements
2340 * of a single-dimensional array "id_test" to the previous element
2341 * (according to "inc"), provided this element belongs to "domain".
2342 * That is, create the affine expression
2344 * { id[x] -> id[x - inc] : x - inc in domain }
2346 static __isl_give isl_multi_pw_aff *map_to_previous(__isl_take isl_id *id_test,
2347 __isl_take isl_set *domain, __isl_take isl_val *inc)
2349 isl_space *space;
2350 isl_local_space *ls;
2351 isl_aff *aff;
2352 isl_multi_pw_aff *prev;
2354 space = isl_set_get_space(domain);
2355 ls = isl_local_space_from_space(space);
2356 aff = isl_aff_var_on_domain(ls, isl_dim_set, 0);
2357 aff = isl_aff_add_constant_val(aff, isl_val_neg(inc));
2358 prev = isl_multi_pw_aff_from_pw_aff(isl_pw_aff_from_aff(aff));
2359 domain = isl_set_preimage_multi_pw_aff(domain,
2360 isl_multi_pw_aff_copy(prev));
2361 prev = isl_multi_pw_aff_intersect_domain(prev, domain);
2362 prev = isl_multi_pw_aff_set_tuple_id(prev, isl_dim_out, id_test);
2364 return prev;
2367 /* Add an implication to "scop" expressing that if an element of
2368 * virtual array "id_test" has value "satisfied" then all previous elements
2369 * of this array also have that value. The set of previous elements
2370 * is bounded by "domain". If "sign" is negative then iterator
2371 * is decreasing and we express that all subsequent array elements
2372 * (but still defined previously) have the same value.
2374 static struct pet_scop *add_implication(struct pet_scop *scop,
2375 __isl_take isl_id *id_test, __isl_take isl_set *domain, int sign,
2376 int satisfied)
2378 isl_space *space;
2379 isl_map *map;
2381 domain = isl_set_set_tuple_id(domain, id_test);
2382 space = isl_set_get_space(domain);
2383 if (sign > 0)
2384 map = isl_map_lex_ge(space);
2385 else
2386 map = isl_map_lex_le(space);
2387 map = isl_map_intersect_range(map, domain);
2388 scop = pet_scop_add_implication(scop, map, satisfied);
2390 return scop;
2393 /* Add a filter to "scop" that imposes that it is only executed
2394 * when the variable identified by "id_test" has a zero value
2395 * for all previous iterations of "domain".
2397 * In particular, add a filter that imposes that the array
2398 * has a zero value at the previous iteration of domain and
2399 * add an implication that implies that it then has that
2400 * value for all previous iterations.
2402 static struct pet_scop *scop_add_break(struct pet_scop *scop,
2403 __isl_take isl_id *id_test, __isl_take isl_set *domain,
2404 __isl_take isl_val *inc)
2406 isl_multi_pw_aff *prev;
2407 int sign = isl_val_sgn(inc);
2409 prev = map_to_previous(isl_id_copy(id_test), isl_set_copy(domain), inc);
2410 scop = add_implication(scop, id_test, domain, sign, 0);
2411 scop = pet_scop_filter(scop, prev, 0);
2413 return scop;
2416 /* Construct a pet_scop for an infinite loop around the given body.
2418 * We extract a pet_scop for the body and then embed it in a loop with
2419 * iteration domain
2421 * { [t] : t >= 0 }
2423 * and schedule
2425 * { [t] -> [t] }
2427 * If the body contains any break, then it is taken into
2428 * account in infinite_domain (if the skip condition is affine)
2429 * or in scop_add_break (if the skip condition is not affine).
2431 * If we were only able to extract part of the body, then simply
2432 * return that part.
2434 struct pet_scop *PetScan::extract_infinite_loop(Stmt *body)
2436 isl_id *id, *id_test;
2437 isl_set *domain;
2438 isl_aff *ident;
2439 struct pet_scop *scop;
2440 bool has_var_break;
2442 scop = extract(body);
2443 if (!scop)
2444 return NULL;
2445 if (partial)
2446 return scop;
2448 id = isl_id_alloc(ctx, "t", NULL);
2449 domain = infinite_domain(isl_id_copy(id), scop);
2450 ident = identity_aff(domain);
2452 has_var_break = pet_scop_has_var_skip(scop, pet_skip_later);
2453 if (has_var_break)
2454 id_test = pet_scop_get_skip_id(scop, pet_skip_later);
2456 scop = pet_scop_embed(scop, isl_set_copy(domain),
2457 isl_map_from_aff(isl_aff_copy(ident)), ident, id);
2458 if (has_var_break)
2459 scop = scop_add_break(scop, id_test, domain, isl_val_one(ctx));
2460 else
2461 isl_set_free(domain);
2463 return scop;
2466 /* Construct a pet_scop for an infinite loop, i.e., a loop of the form
2468 * for (;;)
2469 * body
2472 struct pet_scop *PetScan::extract_infinite_for(ForStmt *stmt)
2474 clear_assignments clear(assigned_value);
2475 clear.TraverseStmt(stmt->getBody());
2477 return extract_infinite_loop(stmt->getBody());
2480 /* Create an index expression for an access to a virtual array
2481 * representing the result of a condition.
2482 * Unlike other accessed data, the id of the array is NULL as
2483 * there is no ValueDecl in the program corresponding to the virtual
2484 * array.
2485 * The array starts out as a scalar, but grows along with the
2486 * statement writing to the array in pet_scop_embed.
2488 static __isl_give isl_multi_pw_aff *create_test_index(isl_ctx *ctx, int test_nr)
2490 isl_space *dim = isl_space_alloc(ctx, 0, 0, 0);
2491 isl_id *id;
2492 char name[50];
2494 snprintf(name, sizeof(name), "__pet_test_%d", test_nr);
2495 id = isl_id_alloc(ctx, name, NULL);
2496 dim = isl_space_set_tuple_id(dim, isl_dim_out, id);
2497 return isl_multi_pw_aff_zero(dim);
2500 /* Add an array with the given extent (range of "index") to the list
2501 * of arrays in "scop" and return the extended pet_scop.
2502 * The array is marked as attaining values 0 and 1 only and
2503 * as each element being assigned at most once.
2505 static struct pet_scop *scop_add_array(struct pet_scop *scop,
2506 __isl_keep isl_multi_pw_aff *index, clang::ASTContext &ast_ctx)
2508 isl_ctx *ctx = isl_multi_pw_aff_get_ctx(index);
2509 isl_space *dim;
2510 struct pet_array *array;
2511 isl_map *access;
2513 if (!scop)
2514 return NULL;
2515 if (!ctx)
2516 goto error;
2518 array = isl_calloc_type(ctx, struct pet_array);
2519 if (!array)
2520 goto error;
2522 access = isl_map_from_multi_pw_aff(isl_multi_pw_aff_copy(index));
2523 array->extent = isl_map_range(access);
2524 dim = isl_space_params_alloc(ctx, 0);
2525 array->context = isl_set_universe(dim);
2526 dim = isl_space_set_alloc(ctx, 0, 1);
2527 array->value_bounds = isl_set_universe(dim);
2528 array->value_bounds = isl_set_lower_bound_si(array->value_bounds,
2529 isl_dim_set, 0, 0);
2530 array->value_bounds = isl_set_upper_bound_si(array->value_bounds,
2531 isl_dim_set, 0, 1);
2532 array->element_type = strdup("int");
2533 array->element_size = ast_ctx.getTypeInfo(ast_ctx.IntTy).first / 8;
2534 array->uniquely_defined = 1;
2536 if (!array->extent || !array->context)
2537 array = pet_array_free(array);
2539 scop = pet_scop_add_array(scop, array);
2541 return scop;
2542 error:
2543 pet_scop_free(scop);
2544 return NULL;
2547 /* Construct a pet_scop for a while loop of the form
2549 * while (pa)
2550 * body
2552 * In particular, construct a scop for an infinite loop around body and
2553 * intersect the domain with the affine expression.
2554 * Note that this intersection may result in an empty loop.
2556 struct pet_scop *PetScan::extract_affine_while(__isl_take isl_pw_aff *pa,
2557 Stmt *body)
2559 struct pet_scop *scop;
2560 isl_set *dom;
2561 isl_set *valid;
2563 valid = isl_pw_aff_domain(isl_pw_aff_copy(pa));
2564 dom = isl_pw_aff_non_zero_set(pa);
2565 scop = extract_infinite_loop(body);
2566 scop = pet_scop_restrict(scop, dom);
2567 scop = pet_scop_restrict_context(scop, valid);
2569 return scop;
2572 /* Construct a scop for a while, given the scops for the condition
2573 * and the body, the filter identifier and the iteration domain of
2574 * the while loop.
2576 * In particular, the scop for the condition is filtered to depend
2577 * on "id_test" evaluating to true for all previous iterations
2578 * of the loop, while the scop for the body is filtered to depend
2579 * on "id_test" evaluating to true for all iterations up to the
2580 * current iteration.
2581 * The actual filter only imposes that this virtual array has
2582 * value one on the previous or the current iteration.
2583 * The fact that this condition also applies to the previous
2584 * iterations is enforced by an implication.
2586 * These filtered scops are then combined into a single scop.
2588 * "sign" is positive if the iterator increases and negative
2589 * if it decreases.
2591 static struct pet_scop *scop_add_while(struct pet_scop *scop_cond,
2592 struct pet_scop *scop_body, __isl_take isl_id *id_test,
2593 __isl_take isl_set *domain, __isl_take isl_val *inc)
2595 isl_ctx *ctx = isl_set_get_ctx(domain);
2596 isl_space *space;
2597 isl_multi_pw_aff *test_index;
2598 isl_multi_pw_aff *prev;
2599 int sign = isl_val_sgn(inc);
2600 struct pet_scop *scop;
2602 prev = map_to_previous(isl_id_copy(id_test), isl_set_copy(domain), inc);
2603 scop_cond = pet_scop_filter(scop_cond, prev, 1);
2605 space = isl_space_map_from_set(isl_set_get_space(domain));
2606 test_index = isl_multi_pw_aff_identity(space);
2607 test_index = isl_multi_pw_aff_set_tuple_id(test_index, isl_dim_out,
2608 isl_id_copy(id_test));
2609 scop_body = pet_scop_filter(scop_body, test_index, 1);
2611 scop = pet_scop_add_seq(ctx, scop_cond, scop_body);
2612 scop = add_implication(scop, id_test, domain, sign, 1);
2614 return scop;
2617 /* Check if the while loop is of the form
2619 * while (affine expression)
2620 * body
2622 * If so, call extract_affine_while to construct a scop.
2624 * Otherwise, construct a generic while scop, with iteration domain
2625 * { [t] : t >= 0 }. The scop consists of two parts, one for
2626 * evaluating the condition and one for the body.
2627 * The schedule is adjusted to reflect that the condition is evaluated
2628 * before the body is executed and the body is filtered to depend
2629 * on the result of the condition evaluating to true on all iterations
2630 * up to the current iteration, while the evaluation the condition itself
2631 * is filtered to depend on the result of the condition evaluating to true
2632 * on all previous iterations.
2633 * The context of the scop representing the body is dropped
2634 * because we don't know how many times the body will be executed,
2635 * if at all.
2637 * If the body contains any break, then it is taken into
2638 * account in infinite_domain (if the skip condition is affine)
2639 * or in scop_add_break (if the skip condition is not affine).
2641 * If we were only able to extract part of the body, then simply
2642 * return that part.
2644 struct pet_scop *PetScan::extract(WhileStmt *stmt)
2646 Expr *cond;
2647 int test_nr, stmt_nr;
2648 isl_id *id, *id_test, *id_break_test;
2649 isl_multi_pw_aff *test_index;
2650 isl_set *domain;
2651 isl_aff *ident;
2652 isl_pw_aff *pa;
2653 struct pet_scop *scop, *scop_body;
2654 bool has_var_break;
2656 cond = stmt->getCond();
2657 if (!cond) {
2658 unsupported(stmt);
2659 return NULL;
2662 clear_assignments clear(assigned_value);
2663 clear.TraverseStmt(stmt->getBody());
2665 pa = try_extract_affine_condition(cond);
2666 if (pa)
2667 return extract_affine_while(pa, stmt->getBody());
2669 if (!allow_nested) {
2670 unsupported(stmt);
2671 return NULL;
2674 test_nr = n_test++;
2675 stmt_nr = n_stmt++;
2676 scop_body = extract(stmt->getBody());
2677 if (partial)
2678 return scop_body;
2680 test_index = create_test_index(ctx, test_nr);
2681 scop = extract_non_affine_condition(cond, stmt_nr,
2682 isl_multi_pw_aff_copy(test_index));
2683 scop = scop_add_array(scop, test_index, ast_context);
2684 id_test = isl_multi_pw_aff_get_tuple_id(test_index, isl_dim_out);
2685 isl_multi_pw_aff_free(test_index);
2687 id = isl_id_alloc(ctx, "t", NULL);
2688 domain = infinite_domain(isl_id_copy(id), scop_body);
2689 ident = identity_aff(domain);
2691 has_var_break = pet_scop_has_var_skip(scop_body, pet_skip_later);
2692 if (has_var_break)
2693 id_break_test = pet_scop_get_skip_id(scop_body, pet_skip_later);
2695 scop = pet_scop_prefix(scop, 0);
2696 scop = pet_scop_embed(scop, isl_set_copy(domain),
2697 isl_map_from_aff(isl_aff_copy(ident)),
2698 isl_aff_copy(ident), isl_id_copy(id));
2699 scop_body = pet_scop_reset_context(scop_body);
2700 scop_body = pet_scop_prefix(scop_body, 1);
2701 scop_body = pet_scop_embed(scop_body, isl_set_copy(domain),
2702 isl_map_from_aff(isl_aff_copy(ident)), ident, id);
2704 if (has_var_break) {
2705 scop = scop_add_break(scop, isl_id_copy(id_break_test),
2706 isl_set_copy(domain), isl_val_one(ctx));
2707 scop_body = scop_add_break(scop_body, id_break_test,
2708 isl_set_copy(domain), isl_val_one(ctx));
2710 scop = scop_add_while(scop, scop_body, id_test, domain,
2711 isl_val_one(ctx));
2713 return scop;
2716 /* Check whether "cond" expresses a simple loop bound
2717 * on the only set dimension.
2718 * In particular, if "up" is set then "cond" should contain only
2719 * upper bounds on the set dimension.
2720 * Otherwise, it should contain only lower bounds.
2722 static bool is_simple_bound(__isl_keep isl_set *cond, __isl_keep isl_val *inc)
2724 if (isl_val_is_pos(inc))
2725 return !isl_set_dim_has_any_lower_bound(cond, isl_dim_set, 0);
2726 else
2727 return !isl_set_dim_has_any_upper_bound(cond, isl_dim_set, 0);
2730 /* Extend a condition on a given iteration of a loop to one that
2731 * imposes the same condition on all previous iterations.
2732 * "domain" expresses the lower [upper] bound on the iterations
2733 * when inc is positive [negative].
2735 * In particular, we construct the condition (when inc is positive)
2737 * forall i' : (domain(i') and i' <= i) => cond(i')
2739 * which is equivalent to
2741 * not exists i' : domain(i') and i' <= i and not cond(i')
2743 * We construct this set by negating cond, applying a map
2745 * { [i'] -> [i] : domain(i') and i' <= i }
2747 * and then negating the result again.
2749 static __isl_give isl_set *valid_for_each_iteration(__isl_take isl_set *cond,
2750 __isl_take isl_set *domain, __isl_take isl_val *inc)
2752 isl_map *previous_to_this;
2754 if (isl_val_is_pos(inc))
2755 previous_to_this = isl_map_lex_le(isl_set_get_space(domain));
2756 else
2757 previous_to_this = isl_map_lex_ge(isl_set_get_space(domain));
2759 previous_to_this = isl_map_intersect_domain(previous_to_this, domain);
2761 cond = isl_set_complement(cond);
2762 cond = isl_set_apply(cond, previous_to_this);
2763 cond = isl_set_complement(cond);
2765 isl_val_free(inc);
2767 return cond;
2770 /* Construct a domain of the form
2772 * [id] -> { : exists a: id = init + a * inc and a >= 0 }
2774 static __isl_give isl_set *strided_domain(__isl_take isl_id *id,
2775 __isl_take isl_pw_aff *init, __isl_take isl_val *inc)
2777 isl_aff *aff;
2778 isl_space *dim;
2779 isl_set *set;
2781 init = isl_pw_aff_insert_dims(init, isl_dim_in, 0, 1);
2782 dim = isl_pw_aff_get_domain_space(init);
2783 aff = isl_aff_zero_on_domain(isl_local_space_from_space(dim));
2784 aff = isl_aff_add_coefficient_val(aff, isl_dim_in, 0, inc);
2785 init = isl_pw_aff_add(init, isl_pw_aff_from_aff(aff));
2787 dim = isl_space_set_alloc(isl_pw_aff_get_ctx(init), 1, 1);
2788 dim = isl_space_set_dim_id(dim, isl_dim_param, 0, id);
2789 aff = isl_aff_zero_on_domain(isl_local_space_from_space(dim));
2790 aff = isl_aff_add_coefficient_si(aff, isl_dim_param, 0, 1);
2792 set = isl_pw_aff_eq_set(isl_pw_aff_from_aff(aff), init);
2794 set = isl_set_lower_bound_si(set, isl_dim_set, 0, 0);
2796 return isl_set_params(set);
2799 /* Assuming "cond" represents a bound on a loop where the loop
2800 * iterator "iv" is incremented (or decremented) by one, check if wrapping
2801 * is possible.
2803 * Under the given assumptions, wrapping is only possible if "cond" allows
2804 * for the last value before wrapping, i.e., 2^width - 1 in case of an
2805 * increasing iterator and 0 in case of a decreasing iterator.
2807 static bool can_wrap(__isl_keep isl_set *cond, ValueDecl *iv,
2808 __isl_keep isl_val *inc)
2810 bool cw;
2811 isl_ctx *ctx;
2812 isl_val *limit;
2813 isl_set *test;
2815 test = isl_set_copy(cond);
2817 ctx = isl_set_get_ctx(test);
2818 if (isl_val_is_neg(inc))
2819 limit = isl_val_zero(ctx);
2820 else {
2821 limit = isl_val_int_from_ui(ctx, get_type_size(iv));
2822 limit = isl_val_2exp(limit);
2823 limit = isl_val_sub_ui(limit, 1);
2826 test = isl_set_fix_val(cond, isl_dim_set, 0, limit);
2827 cw = !isl_set_is_empty(test);
2828 isl_set_free(test);
2830 return cw;
2833 /* Given a one-dimensional space, construct the following affine expression
2834 * on this space
2836 * { [v] -> [v mod 2^width] }
2838 * where width is the number of bits used to represent the values
2839 * of the unsigned variable "iv".
2841 static __isl_give isl_aff *compute_wrapping(__isl_take isl_space *dim,
2842 ValueDecl *iv)
2844 isl_ctx *ctx;
2845 isl_val *mod;
2846 isl_aff *aff;
2848 ctx = isl_space_get_ctx(dim);
2849 mod = isl_val_int_from_ui(ctx, get_type_size(iv));
2850 mod = isl_val_2exp(mod);
2852 aff = isl_aff_zero_on_domain(isl_local_space_from_space(dim));
2853 aff = isl_aff_add_coefficient_si(aff, isl_dim_in, 0, 1);
2854 aff = isl_aff_mod_val(aff, mod);
2856 return aff;
2859 /* Project out the parameter "id" from "set".
2861 static __isl_give isl_set *set_project_out_by_id(__isl_take isl_set *set,
2862 __isl_keep isl_id *id)
2864 int pos;
2866 pos = isl_set_find_dim_by_id(set, isl_dim_param, id);
2867 if (pos >= 0)
2868 set = isl_set_project_out(set, isl_dim_param, pos, 1);
2870 return set;
2873 /* Compute the set of parameters for which "set1" is a subset of "set2".
2875 * set1 is a subset of set2 if
2877 * forall i in set1 : i in set2
2879 * or
2881 * not exists i in set1 and i not in set2
2883 * i.e.,
2885 * not exists i in set1 \ set2
2887 static __isl_give isl_set *enforce_subset(__isl_take isl_set *set1,
2888 __isl_take isl_set *set2)
2890 return isl_set_complement(isl_set_params(isl_set_subtract(set1, set2)));
2893 /* Compute the set of parameter values for which "cond" holds
2894 * on the next iteration for each element of "dom".
2896 * We first construct mapping { [i] -> [i + inc] }, apply that to "dom"
2897 * and then compute the set of parameters for which the result is a subset
2898 * of "cond".
2900 static __isl_give isl_set *valid_on_next(__isl_take isl_set *cond,
2901 __isl_take isl_set *dom, __isl_take isl_val *inc)
2903 isl_space *space;
2904 isl_aff *aff;
2905 isl_map *next;
2907 space = isl_set_get_space(dom);
2908 aff = isl_aff_zero_on_domain(isl_local_space_from_space(space));
2909 aff = isl_aff_add_coefficient_si(aff, isl_dim_in, 0, 1);
2910 aff = isl_aff_add_constant_val(aff, inc);
2911 next = isl_map_from_basic_map(isl_basic_map_from_aff(aff));
2913 dom = isl_set_apply(dom, next);
2915 return enforce_subset(dom, cond);
2918 /* Does "id" refer to a nested access?
2920 static bool is_nested_parameter(__isl_keep isl_id *id)
2922 return id && isl_id_get_user(id) && !isl_id_get_name(id);
2925 /* Does parameter "pos" of "space" refer to a nested access?
2927 static bool is_nested_parameter(__isl_keep isl_space *space, int pos)
2929 bool nested;
2930 isl_id *id;
2932 id = isl_space_get_dim_id(space, isl_dim_param, pos);
2933 nested = is_nested_parameter(id);
2934 isl_id_free(id);
2936 return nested;
2939 /* Does "space" involve any parameters that refer to nested
2940 * accesses, i.e., parameters with no name?
2942 static bool has_nested(__isl_keep isl_space *space)
2944 int nparam;
2946 nparam = isl_space_dim(space, isl_dim_param);
2947 for (int i = 0; i < nparam; ++i)
2948 if (is_nested_parameter(space, i))
2949 return true;
2951 return false;
2954 /* Does "pa" involve any parameters that refer to nested
2955 * accesses, i.e., parameters with no name?
2957 static bool has_nested(__isl_keep isl_pw_aff *pa)
2959 isl_space *space;
2960 bool nested;
2962 space = isl_pw_aff_get_space(pa);
2963 nested = has_nested(space);
2964 isl_space_free(space);
2966 return nested;
2969 /* Construct a pet_scop for a for statement.
2970 * The for loop is required to be of the form
2972 * for (i = init; condition; ++i)
2974 * or
2976 * for (i = init; condition; --i)
2978 * The initialization of the for loop should either be an assignment
2979 * to an integer variable, or a declaration of such a variable with
2980 * initialization.
2982 * The condition is allowed to contain nested accesses, provided
2983 * they are not being written to inside the body of the loop.
2984 * Otherwise, or if the condition is otherwise non-affine, the for loop is
2985 * essentially treated as a while loop, with iteration domain
2986 * { [i] : i >= init }.
2988 * We extract a pet_scop for the body and then embed it in a loop with
2989 * iteration domain and schedule
2991 * { [i] : i >= init and condition' }
2992 * { [i] -> [i] }
2994 * or
2996 * { [i] : i <= init and condition' }
2997 * { [i] -> [-i] }
2999 * Where condition' is equal to condition if the latter is
3000 * a simple upper [lower] bound and a condition that is extended
3001 * to apply to all previous iterations otherwise.
3003 * If the condition is non-affine, then we drop the condition from the
3004 * iteration domain and instead create a separate statement
3005 * for evaluating the condition. The body is then filtered to depend
3006 * on the result of the condition evaluating to true on all iterations
3007 * up to the current iteration, while the evaluation the condition itself
3008 * is filtered to depend on the result of the condition evaluating to true
3009 * on all previous iterations.
3010 * The context of the scop representing the body is dropped
3011 * because we don't know how many times the body will be executed,
3012 * if at all.
3014 * If the stride of the loop is not 1, then "i >= init" is replaced by
3016 * (exists a: i = init + stride * a and a >= 0)
3018 * If the loop iterator i is unsigned, then wrapping may occur.
3019 * We therefore use a virtual iterator instead that does not wrap.
3020 * However, the condition in the code applies
3021 * to the wrapped value, so we need to change condition(i)
3022 * into condition([i % 2^width]). Similarly, we replace all accesses
3023 * to the original iterator by the wrapping of the virtual iterator.
3024 * Note that there may be no need to perform this final wrapping
3025 * if the loop condition (after wrapping) satisfies certain conditions.
3026 * However, the is_simple_bound condition is not enough since it doesn't
3027 * check if there even is an upper bound.
3029 * Wrapping on unsigned iterators can be avoided entirely if
3030 * loop condition is simple, the loop iterator is incremented
3031 * [decremented] by one and the last value before wrapping cannot
3032 * possibly satisfy the loop condition.
3034 * Before extracting a pet_scop from the body we remove all
3035 * assignments in assigned_value to variables that are assigned
3036 * somewhere in the body of the loop.
3038 * Valid parameters for a for loop are those for which the initial
3039 * value itself, the increment on each domain iteration and
3040 * the condition on both the initial value and
3041 * the result of incrementing the iterator for each iteration of the domain
3042 * can be evaluated.
3043 * If the loop condition is non-affine, then we only consider validity
3044 * of the initial value.
3046 * If the body contains any break, then we keep track of it in "skip"
3047 * (if the skip condition is affine) or it is handled in scop_add_break
3048 * (if the skip condition is not affine).
3049 * Note that the affine break condition needs to be considered with
3050 * respect to previous iterations in the virtual domain (if any).
3052 * If we were only able to extract part of the body, then simply
3053 * return that part.
3055 struct pet_scop *PetScan::extract_for(ForStmt *stmt)
3057 BinaryOperator *ass;
3058 Decl *decl;
3059 Stmt *init;
3060 Expr *lhs, *rhs;
3061 ValueDecl *iv;
3062 isl_space *space;
3063 isl_set *domain;
3064 isl_map *sched;
3065 isl_set *cond = NULL;
3066 isl_set *skip = NULL;
3067 isl_id *id, *id_test = NULL, *id_break_test;
3068 struct pet_scop *scop, *scop_cond = NULL;
3069 assigned_value_cache cache(assigned_value);
3070 isl_val *inc;
3071 bool was_assigned;
3072 bool is_one;
3073 bool is_unsigned;
3074 bool is_simple;
3075 bool is_virtual;
3076 bool has_affine_break;
3077 bool has_var_break;
3078 isl_aff *wrap = NULL;
3079 isl_pw_aff *pa, *pa_inc, *init_val;
3080 isl_set *valid_init;
3081 isl_set *valid_cond;
3082 isl_set *valid_cond_init;
3083 isl_set *valid_cond_next;
3084 isl_set *valid_inc;
3085 int stmt_id;
3087 if (!stmt->getInit() && !stmt->getCond() && !stmt->getInc())
3088 return extract_infinite_for(stmt);
3090 init = stmt->getInit();
3091 if (!init) {
3092 unsupported(stmt);
3093 return NULL;
3095 if ((ass = initialization_assignment(init)) != NULL) {
3096 iv = extract_induction_variable(ass);
3097 if (!iv)
3098 return NULL;
3099 lhs = ass->getLHS();
3100 rhs = ass->getRHS();
3101 } else if ((decl = initialization_declaration(init)) != NULL) {
3102 VarDecl *var = extract_induction_variable(init, decl);
3103 if (!var)
3104 return NULL;
3105 iv = var;
3106 rhs = var->getInit();
3107 lhs = create_DeclRefExpr(var);
3108 } else {
3109 unsupported(stmt->getInit());
3110 return NULL;
3113 assigned_value.erase(iv);
3114 clear_assignments clear(assigned_value);
3115 clear.TraverseStmt(stmt->getBody());
3117 was_assigned = assigned_value.find(iv) != assigned_value.end();
3118 clear_assignment(assigned_value, iv);
3119 init_val = extract_affine(rhs);
3120 if (!was_assigned)
3121 assigned_value.erase(iv);
3122 if (!init_val)
3123 return NULL;
3125 pa_inc = extract_increment(stmt, iv);
3126 if (!pa_inc) {
3127 isl_pw_aff_free(init_val);
3128 return NULL;
3131 inc = NULL;
3132 if (isl_pw_aff_n_piece(pa_inc) != 1 ||
3133 isl_pw_aff_foreach_piece(pa_inc, &extract_cst, &inc) < 0) {
3134 isl_pw_aff_free(init_val);
3135 isl_pw_aff_free(pa_inc);
3136 unsupported(stmt->getInc());
3137 isl_val_free(inc);
3138 return NULL;
3141 pa = try_extract_nested_condition(stmt->getCond());
3142 if (allow_nested && (!pa || has_nested(pa)))
3143 stmt_id = n_stmt++;
3145 scop = extract(stmt->getBody());
3146 if (partial) {
3147 isl_pw_aff_free(init_val);
3148 isl_pw_aff_free(pa_inc);
3149 isl_pw_aff_free(pa);
3150 isl_val_free(inc);
3151 return scop;
3154 valid_inc = isl_pw_aff_domain(pa_inc);
3156 is_unsigned = iv->getType()->isUnsignedIntegerType();
3158 id = isl_id_alloc(ctx, iv->getName().str().c_str(), iv);
3160 has_affine_break = scop &&
3161 pet_scop_has_affine_skip(scop, pet_skip_later);
3162 if (has_affine_break)
3163 skip = pet_scop_get_affine_skip_domain(scop, pet_skip_later);
3164 has_var_break = scop && pet_scop_has_var_skip(scop, pet_skip_later);
3165 if (has_var_break)
3166 id_break_test = pet_scop_get_skip_id(scop, pet_skip_later);
3168 if (pa && !is_nested_allowed(pa, scop)) {
3169 isl_pw_aff_free(pa);
3170 pa = NULL;
3173 if (!allow_nested && !pa)
3174 pa = try_extract_affine_condition(stmt->getCond());
3175 valid_cond = isl_pw_aff_domain(isl_pw_aff_copy(pa));
3176 cond = isl_pw_aff_non_zero_set(pa);
3177 if (allow_nested && !cond) {
3178 isl_multi_pw_aff *test_index;
3179 int save_n_stmt = n_stmt;
3180 test_index = create_test_index(ctx, n_test++);
3181 n_stmt = stmt_id;
3182 scop_cond = extract_non_affine_condition(stmt->getCond(),
3183 n_stmt++, isl_multi_pw_aff_copy(test_index));
3184 n_stmt = save_n_stmt;
3185 scop_cond = scop_add_array(scop_cond, test_index, ast_context);
3186 id_test = isl_multi_pw_aff_get_tuple_id(test_index,
3187 isl_dim_out);
3188 isl_multi_pw_aff_free(test_index);
3189 scop_cond = pet_scop_prefix(scop_cond, 0);
3190 scop = pet_scop_reset_context(scop);
3191 scop = pet_scop_prefix(scop, 1);
3192 cond = isl_set_universe(isl_space_set_alloc(ctx, 0, 0));
3195 cond = embed(cond, isl_id_copy(id));
3196 skip = embed(skip, isl_id_copy(id));
3197 valid_cond = isl_set_coalesce(valid_cond);
3198 valid_cond = embed(valid_cond, isl_id_copy(id));
3199 valid_inc = embed(valid_inc, isl_id_copy(id));
3200 is_one = isl_val_is_one(inc) || isl_val_is_negone(inc);
3201 is_virtual = is_unsigned && (!is_one || can_wrap(cond, iv, inc));
3203 valid_cond_init = enforce_subset(
3204 isl_set_from_pw_aff(isl_pw_aff_copy(init_val)),
3205 isl_set_copy(valid_cond));
3206 if (is_one && !is_virtual) {
3207 isl_pw_aff_free(init_val);
3208 pa = extract_comparison(isl_val_is_pos(inc) ? BO_GE : BO_LE,
3209 lhs, rhs, init);
3210 valid_init = isl_pw_aff_domain(isl_pw_aff_copy(pa));
3211 valid_init = set_project_out_by_id(valid_init, id);
3212 domain = isl_pw_aff_non_zero_set(pa);
3213 } else {
3214 valid_init = isl_pw_aff_domain(isl_pw_aff_copy(init_val));
3215 domain = strided_domain(isl_id_copy(id), init_val,
3216 isl_val_copy(inc));
3219 domain = embed(domain, isl_id_copy(id));
3220 if (is_virtual) {
3221 isl_map *rev_wrap;
3222 wrap = compute_wrapping(isl_set_get_space(cond), iv);
3223 rev_wrap = isl_map_from_aff(isl_aff_copy(wrap));
3224 rev_wrap = isl_map_reverse(rev_wrap);
3225 cond = isl_set_apply(cond, isl_map_copy(rev_wrap));
3226 skip = isl_set_apply(skip, isl_map_copy(rev_wrap));
3227 valid_cond = isl_set_apply(valid_cond, isl_map_copy(rev_wrap));
3228 valid_inc = isl_set_apply(valid_inc, rev_wrap);
3230 is_simple = is_simple_bound(cond, inc);
3231 if (!is_simple) {
3232 cond = isl_set_gist(cond, isl_set_copy(domain));
3233 is_simple = is_simple_bound(cond, inc);
3235 if (!is_simple)
3236 cond = valid_for_each_iteration(cond,
3237 isl_set_copy(domain), isl_val_copy(inc));
3238 domain = isl_set_intersect(domain, cond);
3239 if (has_affine_break) {
3240 skip = isl_set_intersect(skip , isl_set_copy(domain));
3241 skip = after(skip, isl_val_sgn(inc));
3242 domain = isl_set_subtract(domain, skip);
3244 domain = isl_set_set_dim_id(domain, isl_dim_set, 0, isl_id_copy(id));
3245 space = isl_space_from_domain(isl_set_get_space(domain));
3246 space = isl_space_add_dims(space, isl_dim_out, 1);
3247 sched = isl_map_universe(space);
3248 if (isl_val_is_pos(inc))
3249 sched = isl_map_equate(sched, isl_dim_in, 0, isl_dim_out, 0);
3250 else
3251 sched = isl_map_oppose(sched, isl_dim_in, 0, isl_dim_out, 0);
3253 valid_cond_next = valid_on_next(valid_cond, isl_set_copy(domain),
3254 isl_val_copy(inc));
3255 valid_inc = enforce_subset(isl_set_copy(domain), valid_inc);
3257 if (!is_virtual)
3258 wrap = identity_aff(domain);
3260 scop_cond = pet_scop_embed(scop_cond, isl_set_copy(domain),
3261 isl_map_copy(sched), isl_aff_copy(wrap), isl_id_copy(id));
3262 scop = pet_scop_embed(scop, isl_set_copy(domain), sched, wrap, id);
3263 scop = resolve_nested(scop);
3264 if (has_var_break)
3265 scop = scop_add_break(scop, id_break_test, isl_set_copy(domain),
3266 isl_val_copy(inc));
3267 if (id_test) {
3268 scop = scop_add_while(scop_cond, scop, id_test, domain,
3269 isl_val_copy(inc));
3270 isl_set_free(valid_inc);
3271 } else {
3272 scop = pet_scop_restrict_context(scop, valid_inc);
3273 scop = pet_scop_restrict_context(scop, valid_cond_next);
3274 scop = pet_scop_restrict_context(scop, valid_cond_init);
3275 isl_set_free(domain);
3277 clear_assignment(assigned_value, iv);
3279 isl_val_free(inc);
3281 scop = pet_scop_restrict_context(scop, valid_init);
3283 return scop;
3286 /* Try and construct a pet_scop corresponding to a compound statement.
3288 * "skip_declarations" is set if we should skip initial declarations
3289 * in the children of the compound statements. This then implies
3290 * that this sequence of children should not be treated as a block
3291 * since the initial statements may be skipped.
3293 struct pet_scop *PetScan::extract(CompoundStmt *stmt, bool skip_declarations)
3295 return extract(stmt->children(), !skip_declarations, skip_declarations);
3298 /* Does parameter "pos" of "map" refer to a nested access?
3300 static bool is_nested_parameter(__isl_keep isl_map *map, int pos)
3302 bool nested;
3303 isl_id *id;
3305 id = isl_map_get_dim_id(map, isl_dim_param, pos);
3306 nested = is_nested_parameter(id);
3307 isl_id_free(id);
3309 return nested;
3312 /* How many parameters of "space" refer to nested accesses, i.e., have no name?
3314 static int n_nested_parameter(__isl_keep isl_space *space)
3316 int n = 0;
3317 int nparam;
3319 nparam = isl_space_dim(space, isl_dim_param);
3320 for (int i = 0; i < nparam; ++i)
3321 if (is_nested_parameter(space, i))
3322 ++n;
3324 return n;
3327 /* How many parameters of "map" refer to nested accesses, i.e., have no name?
3329 static int n_nested_parameter(__isl_keep isl_map *map)
3331 isl_space *space;
3332 int n;
3334 space = isl_map_get_space(map);
3335 n = n_nested_parameter(space);
3336 isl_space_free(space);
3338 return n;
3341 /* For each nested access parameter in "space",
3342 * construct a corresponding pet_expr, place it in args and
3343 * record its position in "param2pos".
3344 * "n_arg" is the number of elements that are already in args.
3345 * The position recorded in "param2pos" takes this number into account.
3346 * If the pet_expr corresponding to a parameter is identical to
3347 * the pet_expr corresponding to an earlier parameter, then these two
3348 * parameters are made to refer to the same element in args.
3350 * Return the final number of elements in args or -1 if an error has occurred.
3352 int PetScan::extract_nested(__isl_keep isl_space *space,
3353 int n_arg, struct pet_expr **args, std::map<int,int> &param2pos)
3355 int nparam;
3357 nparam = isl_space_dim(space, isl_dim_param);
3358 for (int i = 0; i < nparam; ++i) {
3359 int j;
3360 isl_id *id = isl_space_get_dim_id(space, isl_dim_param, i);
3361 Expr *nested;
3363 if (!is_nested_parameter(id)) {
3364 isl_id_free(id);
3365 continue;
3368 nested = (Expr *) isl_id_get_user(id);
3369 args[n_arg] = extract_expr(nested);
3370 isl_id_free(id);
3371 if (!args[n_arg])
3372 return -1;
3374 for (j = 0; j < n_arg; ++j)
3375 if (pet_expr_is_equal(args[j], args[n_arg]))
3376 break;
3378 if (j < n_arg) {
3379 pet_expr_free(args[n_arg]);
3380 args[n_arg] = NULL;
3381 param2pos[i] = j;
3382 } else
3383 param2pos[i] = n_arg++;
3386 return n_arg;
3389 /* For each nested access parameter in the access relations in "expr",
3390 * construct a corresponding pet_expr, place it in expr->args and
3391 * record its position in "param2pos".
3392 * n is the number of nested access parameters.
3394 struct pet_expr *PetScan::extract_nested(struct pet_expr *expr, int n,
3395 std::map<int,int> &param2pos)
3397 isl_space *space;
3399 expr->args = isl_calloc_array(ctx, struct pet_expr *, n);
3400 expr->n_arg = n;
3401 if (!expr->args)
3402 goto error;
3404 space = isl_map_get_space(expr->acc.access);
3405 n = extract_nested(space, 0, expr->args, param2pos);
3406 isl_space_free(space);
3408 if (n < 0)
3409 goto error;
3411 expr->n_arg = n;
3412 return expr;
3413 error:
3414 pet_expr_free(expr);
3415 return NULL;
3418 /* Look for parameters in any access relation in "expr" that
3419 * refer to nested accesses. In particular, these are
3420 * parameters with no name.
3422 * If there are any such parameters, then the domain of the index
3423 * expression and the access relation, which is still [] at this point,
3424 * is replaced by [[] -> [t_1,...,t_n]], with n the number of these parameters
3425 * (after identifying identical nested accesses).
3427 * This transformation is performed in several steps.
3428 * We first extract the arguments in extract_nested.
3429 * param2pos maps the original parameter position to the position
3430 * of the argument.
3431 * Then we move these parameters to input dimension.
3432 * t2pos maps the positions of these temporary input dimensions
3433 * to the positions of the corresponding arguments.
3434 * Finally, we express there temporary dimensions in term of the domain
3435 * [[] -> [t_1,...,t_n]] and precompose index expression and access
3436 * relations with this function.
3438 struct pet_expr *PetScan::resolve_nested(struct pet_expr *expr)
3440 int n;
3441 int nparam;
3442 isl_space *space;
3443 isl_local_space *ls;
3444 isl_aff *aff;
3445 isl_multi_aff *ma;
3446 std::map<int,int> param2pos;
3447 std::map<int,int> t2pos;
3449 if (!expr)
3450 return expr;
3452 for (int i = 0; i < expr->n_arg; ++i) {
3453 expr->args[i] = resolve_nested(expr->args[i]);
3454 if (!expr->args[i]) {
3455 pet_expr_free(expr);
3456 return NULL;
3460 if (expr->type != pet_expr_access)
3461 return expr;
3463 n = n_nested_parameter(expr->acc.access);
3464 if (n == 0)
3465 return expr;
3467 expr = extract_nested(expr, n, param2pos);
3468 if (!expr)
3469 return NULL;
3471 expr = pet_expr_access_align_params(expr);
3472 if (!expr)
3473 return NULL;
3474 nparam = isl_map_dim(expr->acc.access, isl_dim_param);
3476 n = 0;
3477 for (int i = nparam - 1; i >= 0; --i) {
3478 isl_id *id = isl_map_get_dim_id(expr->acc.access,
3479 isl_dim_param, i);
3480 if (!is_nested_parameter(id)) {
3481 isl_id_free(id);
3482 continue;
3485 expr->acc.access = isl_map_move_dims(expr->acc.access,
3486 isl_dim_in, n, isl_dim_param, i, 1);
3487 expr->acc.index = isl_multi_pw_aff_move_dims(expr->acc.index,
3488 isl_dim_in, n, isl_dim_param, i, 1);
3489 t2pos[n] = param2pos[i];
3490 n++;
3492 isl_id_free(id);
3495 space = isl_multi_pw_aff_get_space(expr->acc.index);
3496 space = isl_space_set_from_params(isl_space_params(space));
3497 space = isl_space_add_dims(space, isl_dim_set, expr->n_arg);
3498 space = isl_space_wrap(isl_space_from_range(space));
3499 ls = isl_local_space_from_space(isl_space_copy(space));
3500 space = isl_space_from_domain(space);
3501 space = isl_space_add_dims(space, isl_dim_out, n);
3502 ma = isl_multi_aff_zero(space);
3504 for (int i = 0; i < n; ++i) {
3505 aff = isl_aff_var_on_domain(isl_local_space_copy(ls),
3506 isl_dim_set, t2pos[i]);
3507 ma = isl_multi_aff_set_aff(ma, i, aff);
3509 isl_local_space_free(ls);
3511 expr->acc.access = isl_map_preimage_domain_multi_aff(expr->acc.access,
3512 isl_multi_aff_copy(ma));
3513 expr->acc.index = isl_multi_pw_aff_pullback_multi_aff(expr->acc.index,
3514 ma);
3516 return expr;
3519 /* Return the file offset of the expansion location of "Loc".
3521 static unsigned getExpansionOffset(SourceManager &SM, SourceLocation Loc)
3523 return SM.getFileOffset(SM.getExpansionLoc(Loc));
3526 #ifdef HAVE_FINDLOCATIONAFTERTOKEN
3528 /* Return a SourceLocation for the location after the first semicolon
3529 * after "loc". If Lexer::findLocationAfterToken is available, we simply
3530 * call it and also skip trailing spaces and newline.
3532 static SourceLocation location_after_semi(SourceLocation loc, SourceManager &SM,
3533 const LangOptions &LO)
3535 return Lexer::findLocationAfterToken(loc, tok::semi, SM, LO, true);
3538 #else
3540 /* Return a SourceLocation for the location after the first semicolon
3541 * after "loc". If Lexer::findLocationAfterToken is not available,
3542 * we look in the underlying character data for the first semicolon.
3544 static SourceLocation location_after_semi(SourceLocation loc, SourceManager &SM,
3545 const LangOptions &LO)
3547 const char *semi;
3548 const char *s = SM.getCharacterData(loc);
3550 semi = strchr(s, ';');
3551 if (!semi)
3552 return SourceLocation();
3553 return loc.getFileLocWithOffset(semi + 1 - s);
3556 #endif
3558 /* If the token at "loc" is the first token on the line, then return
3559 * a location referring to the start of the line.
3560 * Otherwise, return "loc".
3562 * This function is used to extend a scop to the start of the line
3563 * if the first token of the scop is also the first token on the line.
3565 * We look for the first token on the line. If its location is equal to "loc",
3566 * then the latter is the location of the first token on the line.
3568 static SourceLocation move_to_start_of_line_if_first_token(SourceLocation loc,
3569 SourceManager &SM, const LangOptions &LO)
3571 std::pair<FileID, unsigned> file_offset_pair;
3572 llvm::StringRef file;
3573 const char *pos;
3574 Token tok;
3575 SourceLocation token_loc, line_loc;
3576 int col;
3578 loc = SM.getExpansionLoc(loc);
3579 col = SM.getExpansionColumnNumber(loc);
3580 line_loc = loc.getLocWithOffset(1 - col);
3581 file_offset_pair = SM.getDecomposedLoc(line_loc);
3582 file = SM.getBufferData(file_offset_pair.first, NULL);
3583 pos = file.data() + file_offset_pair.second;
3585 Lexer lexer(SM.getLocForStartOfFile(file_offset_pair.first), LO,
3586 file.begin(), pos, file.end());
3587 lexer.LexFromRawLexer(tok);
3588 token_loc = tok.getLocation();
3590 if (token_loc == loc)
3591 return line_loc;
3592 else
3593 return loc;
3596 /* Update start and end of "scop" to include the region covered by "range".
3597 * If "skip_semi" is set, then we assume "range" is followed by
3598 * a semicolon and also include this semicolon.
3600 struct pet_scop *PetScan::update_scop_start_end(struct pet_scop *scop,
3601 SourceRange range, bool skip_semi)
3603 SourceLocation loc = range.getBegin();
3604 SourceManager &SM = PP.getSourceManager();
3605 const LangOptions &LO = PP.getLangOpts();
3606 unsigned start, end;
3608 loc = move_to_start_of_line_if_first_token(loc, SM, LO);
3609 start = getExpansionOffset(SM, loc);
3610 loc = range.getEnd();
3611 if (skip_semi)
3612 loc = location_after_semi(loc, SM, LO);
3613 else
3614 loc = PP.getLocForEndOfToken(loc);
3615 end = getExpansionOffset(SM, loc);
3617 scop = pet_scop_update_start_end(scop, start, end);
3618 return scop;
3621 /* Convert a top-level pet_expr to a pet_scop with one statement.
3622 * This mainly involves resolving nested expression parameters
3623 * and setting the name of the iteration space.
3624 * The name is given by "label" if it is non-NULL. Otherwise,
3625 * it is of the form S_<n_stmt>.
3626 * start and end of the pet_scop are derived from those of "stmt".
3627 * If "stmt" is an expression statement, then its range does not
3628 * include the semicolon, while it should be included in the pet_scop.
3630 struct pet_scop *PetScan::extract(Stmt *stmt, struct pet_expr *expr,
3631 __isl_take isl_id *label)
3633 struct pet_stmt *ps;
3634 struct pet_scop *scop;
3635 SourceLocation loc = stmt->getLocStart();
3636 int line = PP.getSourceManager().getExpansionLineNumber(loc);
3637 bool skip_semi;
3639 expr = resolve_nested(expr);
3640 ps = pet_stmt_from_pet_expr(ctx, line, label, n_stmt++, expr);
3641 scop = pet_scop_from_pet_stmt(ctx, ps);
3643 skip_semi = isa<Expr>(stmt);
3644 scop = update_scop_start_end(scop, stmt->getSourceRange(), skip_semi);
3645 return scop;
3648 /* Check if we can extract an affine expression from "expr".
3649 * Return the expressions as an isl_pw_aff if we can and NULL otherwise.
3650 * We turn on autodetection so that we won't generate any warnings
3651 * and turn off nesting, so that we won't accept any non-affine constructs.
3653 __isl_give isl_pw_aff *PetScan::try_extract_affine(Expr *expr)
3655 isl_pw_aff *pwaff;
3656 int save_autodetect = options->autodetect;
3657 bool save_nesting = nesting_enabled;
3659 options->autodetect = 1;
3660 nesting_enabled = false;
3662 pwaff = extract_affine(expr);
3664 options->autodetect = save_autodetect;
3665 nesting_enabled = save_nesting;
3667 return pwaff;
3670 /* Check whether "expr" is an affine expression.
3672 bool PetScan::is_affine(Expr *expr)
3674 isl_pw_aff *pwaff;
3676 pwaff = try_extract_affine(expr);
3677 isl_pw_aff_free(pwaff);
3679 return pwaff != NULL;
3682 /* Check if we can extract an affine constraint from "expr".
3683 * Return the constraint as an isl_set if we can and NULL otherwise.
3684 * We turn on autodetection so that we won't generate any warnings
3685 * and turn off nesting, so that we won't accept any non-affine constructs.
3687 __isl_give isl_pw_aff *PetScan::try_extract_affine_condition(Expr *expr)
3689 isl_pw_aff *cond;
3690 int save_autodetect = options->autodetect;
3691 bool save_nesting = nesting_enabled;
3693 options->autodetect = 1;
3694 nesting_enabled = false;
3696 cond = extract_condition(expr);
3698 options->autodetect = save_autodetect;
3699 nesting_enabled = save_nesting;
3701 return cond;
3704 /* Check whether "expr" is an affine constraint.
3706 bool PetScan::is_affine_condition(Expr *expr)
3708 isl_pw_aff *cond;
3710 cond = try_extract_affine_condition(expr);
3711 isl_pw_aff_free(cond);
3713 return cond != NULL;
3716 /* Check if we can extract a condition from "expr".
3717 * Return the condition as an isl_pw_aff if we can and NULL otherwise.
3718 * If allow_nested is set, then the condition may involve parameters
3719 * corresponding to nested accesses.
3720 * We turn on autodetection so that we won't generate any warnings.
3722 __isl_give isl_pw_aff *PetScan::try_extract_nested_condition(Expr *expr)
3724 isl_pw_aff *cond;
3725 int save_autodetect = options->autodetect;
3726 bool save_nesting = nesting_enabled;
3728 options->autodetect = 1;
3729 nesting_enabled = allow_nested;
3730 cond = extract_condition(expr);
3732 options->autodetect = save_autodetect;
3733 nesting_enabled = save_nesting;
3735 return cond;
3738 /* If the top-level expression of "stmt" is an assignment, then
3739 * return that assignment as a BinaryOperator.
3740 * Otherwise return NULL.
3742 static BinaryOperator *top_assignment_or_null(Stmt *stmt)
3744 BinaryOperator *ass;
3746 if (!stmt)
3747 return NULL;
3748 if (stmt->getStmtClass() != Stmt::BinaryOperatorClass)
3749 return NULL;
3751 ass = cast<BinaryOperator>(stmt);
3752 if(ass->getOpcode() != BO_Assign)
3753 return NULL;
3755 return ass;
3758 /* Check if the given if statement is a conditional assignement
3759 * with a non-affine condition. If so, construct a pet_scop
3760 * corresponding to this conditional assignment. Otherwise return NULL.
3762 * In particular we check if "stmt" is of the form
3764 * if (condition)
3765 * a = f(...);
3766 * else
3767 * a = g(...);
3769 * where a is some array or scalar access.
3770 * The constructed pet_scop then corresponds to the expression
3772 * a = condition ? f(...) : g(...)
3774 * All access relations in f(...) are intersected with condition
3775 * while all access relation in g(...) are intersected with the complement.
3777 struct pet_scop *PetScan::extract_conditional_assignment(IfStmt *stmt)
3779 BinaryOperator *ass_then, *ass_else;
3780 isl_multi_pw_aff *write_then, *write_else;
3781 isl_set *cond, *comp;
3782 isl_multi_pw_aff *index;
3783 isl_pw_aff *pa;
3784 int equal;
3785 struct pet_expr *pe_cond, *pe_then, *pe_else, *pe, *pe_write;
3786 bool save_nesting = nesting_enabled;
3788 if (!options->detect_conditional_assignment)
3789 return NULL;
3791 ass_then = top_assignment_or_null(stmt->getThen());
3792 ass_else = top_assignment_or_null(stmt->getElse());
3794 if (!ass_then || !ass_else)
3795 return NULL;
3797 if (is_affine_condition(stmt->getCond()))
3798 return NULL;
3800 write_then = extract_index(ass_then->getLHS());
3801 write_else = extract_index(ass_else->getLHS());
3803 equal = isl_multi_pw_aff_plain_is_equal(write_then, write_else);
3804 isl_multi_pw_aff_free(write_else);
3805 if (equal < 0 || !equal) {
3806 isl_multi_pw_aff_free(write_then);
3807 return NULL;
3810 nesting_enabled = allow_nested;
3811 pa = extract_condition(stmt->getCond());
3812 nesting_enabled = save_nesting;
3813 cond = isl_pw_aff_non_zero_set(isl_pw_aff_copy(pa));
3814 comp = isl_pw_aff_zero_set(isl_pw_aff_copy(pa));
3815 index = isl_multi_pw_aff_from_range(isl_multi_pw_aff_from_pw_aff(pa));
3817 pe_cond = pet_expr_from_index(index);
3819 pe_then = extract_expr(ass_then->getRHS());
3820 pe_then = pet_expr_restrict(pe_then, cond);
3821 pe_else = extract_expr(ass_else->getRHS());
3822 pe_else = pet_expr_restrict(pe_else, comp);
3824 pe = pet_expr_new_ternary(ctx, pe_cond, pe_then, pe_else);
3825 pe_write = pet_expr_from_index_and_depth(write_then,
3826 extract_depth(write_then));
3827 if (pe_write) {
3828 pe_write->acc.write = 1;
3829 pe_write->acc.read = 0;
3831 pe = pet_expr_new_binary(ctx, pet_op_assign, pe_write, pe);
3832 return extract(stmt, pe);
3835 /* Create a pet_scop with a single statement with name S_<stmt_nr>,
3836 * evaluating "cond" and writing the result to a virtual scalar,
3837 * as expressed by "index".
3839 struct pet_scop *PetScan::extract_non_affine_condition(Expr *cond, int stmt_nr,
3840 __isl_take isl_multi_pw_aff *index)
3842 struct pet_expr *expr, *write;
3843 struct pet_stmt *ps;
3844 SourceLocation loc = cond->getLocStart();
3845 int line = PP.getSourceManager().getExpansionLineNumber(loc);
3847 write = pet_expr_from_index(index);
3848 if (write) {
3849 write->acc.write = 1;
3850 write->acc.read = 0;
3852 expr = extract_expr(cond);
3853 expr = resolve_nested(expr);
3854 expr = pet_expr_new_binary(ctx, pet_op_assign, write, expr);
3855 ps = pet_stmt_from_pet_expr(ctx, line, NULL, stmt_nr, expr);
3856 return pet_scop_from_pet_stmt(ctx, ps);
3859 extern "C" {
3860 static struct pet_expr *embed_access(struct pet_expr *expr, void *user);
3863 /* Precompose the access relation and the index expression associated
3864 * to "expr" with the function pointed to by "user",
3865 * thereby embedding the access relation in the domain of this function.
3866 * The initial domain of the access relation and the index expression
3867 * is the zero-dimensional domain.
3869 static struct pet_expr *embed_access(struct pet_expr *expr, void *user)
3871 isl_multi_aff *ma = (isl_multi_aff *) user;
3873 expr->acc.access = isl_map_preimage_domain_multi_aff(expr->acc.access,
3874 isl_multi_aff_copy(ma));
3875 expr->acc.index = isl_multi_pw_aff_pullback_multi_aff(expr->acc.index,
3876 isl_multi_aff_copy(ma));
3877 if (!expr->acc.access || !expr->acc.index)
3878 goto error;
3880 return expr;
3881 error:
3882 pet_expr_free(expr);
3883 return NULL;
3886 /* Precompose all access relations in "expr" with "ma", thereby
3887 * embedding them in the domain of "ma".
3889 static struct pet_expr *embed(struct pet_expr *expr,
3890 __isl_keep isl_multi_aff *ma)
3892 return pet_expr_map_access(expr, &embed_access, ma);
3895 /* How many parameters of "set" refer to nested accesses, i.e., have no name?
3897 static int n_nested_parameter(__isl_keep isl_set *set)
3899 isl_space *space;
3900 int n;
3902 space = isl_set_get_space(set);
3903 n = n_nested_parameter(space);
3904 isl_space_free(space);
3906 return n;
3909 /* Remove all parameters from "map" that refer to nested accesses.
3911 static __isl_give isl_map *remove_nested_parameters(__isl_take isl_map *map)
3913 int nparam;
3914 isl_space *space;
3916 space = isl_map_get_space(map);
3917 nparam = isl_space_dim(space, isl_dim_param);
3918 for (int i = nparam - 1; i >= 0; --i)
3919 if (is_nested_parameter(space, i))
3920 map = isl_map_project_out(map, isl_dim_param, i, 1);
3921 isl_space_free(space);
3923 return map;
3926 /* Remove all parameters from "mpa" that refer to nested accesses.
3928 static __isl_give isl_multi_pw_aff *remove_nested_parameters(
3929 __isl_take isl_multi_pw_aff *mpa)
3931 int nparam;
3932 isl_space *space;
3934 space = isl_multi_pw_aff_get_space(mpa);
3935 nparam = isl_space_dim(space, isl_dim_param);
3936 for (int i = nparam - 1; i >= 0; --i) {
3937 if (!is_nested_parameter(space, i))
3938 continue;
3939 mpa = isl_multi_pw_aff_drop_dims(mpa, isl_dim_param, i, 1);
3941 isl_space_free(space);
3943 return mpa;
3946 /* Remove all parameters from the index expression and access relation of "expr"
3947 * that refer to nested accesses.
3949 static struct pet_expr *remove_nested_parameters(struct pet_expr *expr)
3951 expr->acc.access = remove_nested_parameters(expr->acc.access);
3952 expr->acc.index = remove_nested_parameters(expr->acc.index);
3953 if (!expr->acc.access || !expr->acc.index)
3954 goto error;
3956 return expr;
3957 error:
3958 pet_expr_free(expr);
3959 return NULL;
3962 extern "C" {
3963 static struct pet_expr *expr_remove_nested_parameters(
3964 struct pet_expr *expr, void *user);
3967 static struct pet_expr *expr_remove_nested_parameters(
3968 struct pet_expr *expr, void *user)
3970 return remove_nested_parameters(expr);
3973 /* Remove all nested access parameters from the schedule and all
3974 * accesses of "stmt".
3975 * There is no need to remove them from the domain as these parameters
3976 * have already been removed from the domain when this function is called.
3978 static struct pet_stmt *remove_nested_parameters(struct pet_stmt *stmt)
3980 if (!stmt)
3981 return NULL;
3982 stmt->schedule = remove_nested_parameters(stmt->schedule);
3983 stmt->body = pet_expr_map_access(stmt->body,
3984 &expr_remove_nested_parameters, NULL);
3985 if (!stmt->schedule || !stmt->body)
3986 goto error;
3987 for (int i = 0; i < stmt->n_arg; ++i) {
3988 stmt->args[i] = pet_expr_map_access(stmt->args[i],
3989 &expr_remove_nested_parameters, NULL);
3990 if (!stmt->args[i])
3991 goto error;
3994 return stmt;
3995 error:
3996 pet_stmt_free(stmt);
3997 return NULL;
4000 /* For each nested access parameter in the domain of "stmt",
4001 * construct a corresponding pet_expr, place it before the original
4002 * elements in stmt->args and record its position in "param2pos".
4003 * n is the number of nested access parameters.
4005 struct pet_stmt *PetScan::extract_nested(struct pet_stmt *stmt, int n,
4006 std::map<int,int> &param2pos)
4008 int i;
4009 isl_space *space;
4010 int n_arg;
4011 struct pet_expr **args;
4013 n_arg = stmt->n_arg;
4014 args = isl_calloc_array(ctx, struct pet_expr *, n + n_arg);
4015 if (!args)
4016 goto error;
4018 space = isl_set_get_space(stmt->domain);
4019 n_arg = extract_nested(space, 0, args, param2pos);
4020 isl_space_free(space);
4022 if (n_arg < 0)
4023 goto error;
4025 for (i = 0; i < stmt->n_arg; ++i)
4026 args[n_arg + i] = stmt->args[i];
4027 free(stmt->args);
4028 stmt->args = args;
4029 stmt->n_arg += n_arg;
4031 return stmt;
4032 error:
4033 if (args) {
4034 for (i = 0; i < n; ++i)
4035 pet_expr_free(args[i]);
4036 free(args);
4038 pet_stmt_free(stmt);
4039 return NULL;
4042 /* Check whether any of the arguments i of "stmt" starting at position "n"
4043 * is equal to one of the first "n" arguments j.
4044 * If so, combine the constraints on arguments i and j and remove
4045 * argument i.
4047 static struct pet_stmt *remove_duplicate_arguments(struct pet_stmt *stmt, int n)
4049 int i, j;
4050 isl_map *map;
4052 if (!stmt)
4053 return NULL;
4054 if (n == 0)
4055 return stmt;
4056 if (n == stmt->n_arg)
4057 return stmt;
4059 map = isl_set_unwrap(stmt->domain);
4061 for (i = stmt->n_arg - 1; i >= n; --i) {
4062 for (j = 0; j < n; ++j)
4063 if (pet_expr_is_equal(stmt->args[i], stmt->args[j]))
4064 break;
4065 if (j >= n)
4066 continue;
4068 map = isl_map_equate(map, isl_dim_out, i, isl_dim_out, j);
4069 map = isl_map_project_out(map, isl_dim_out, i, 1);
4071 pet_expr_free(stmt->args[i]);
4072 for (j = i; j + 1 < stmt->n_arg; ++j)
4073 stmt->args[j] = stmt->args[j + 1];
4074 stmt->n_arg--;
4077 stmt->domain = isl_map_wrap(map);
4078 if (!stmt->domain)
4079 goto error;
4080 return stmt;
4081 error:
4082 pet_stmt_free(stmt);
4083 return NULL;
4086 /* Look for parameters in the iteration domain of "stmt" that
4087 * refer to nested accesses. In particular, these are
4088 * parameters with no name.
4090 * If there are any such parameters, then as many extra variables
4091 * (after identifying identical nested accesses) are inserted in the
4092 * range of the map wrapped inside the domain, before the original variables.
4093 * If the original domain is not a wrapped map, then a new wrapped
4094 * map is created with zero output dimensions.
4095 * The parameters are then equated to the corresponding output dimensions
4096 * and subsequently projected out, from the iteration domain,
4097 * the schedule and the access relations.
4098 * For each of the output dimensions, a corresponding argument
4099 * expression is inserted. Initially they are created with
4100 * a zero-dimensional domain, so they have to be embedded
4101 * in the current iteration domain.
4102 * param2pos maps the position of the parameter to the position
4103 * of the corresponding output dimension in the wrapped map.
4105 struct pet_stmt *PetScan::resolve_nested(struct pet_stmt *stmt)
4107 int n;
4108 int nparam;
4109 unsigned n_arg;
4110 isl_map *map;
4111 isl_space *space;
4112 isl_multi_aff *ma;
4113 std::map<int,int> param2pos;
4115 if (!stmt)
4116 return NULL;
4118 n = n_nested_parameter(stmt->domain);
4119 if (n == 0)
4120 return stmt;
4122 n_arg = stmt->n_arg;
4123 stmt = extract_nested(stmt, n, param2pos);
4124 if (!stmt)
4125 return NULL;
4127 n = stmt->n_arg - n_arg;
4128 nparam = isl_set_dim(stmt->domain, isl_dim_param);
4129 if (isl_set_is_wrapping(stmt->domain))
4130 map = isl_set_unwrap(stmt->domain);
4131 else
4132 map = isl_map_from_domain(stmt->domain);
4133 map = isl_map_insert_dims(map, isl_dim_out, 0, n);
4135 for (int i = nparam - 1; i >= 0; --i) {
4136 isl_id *id;
4138 if (!is_nested_parameter(map, i))
4139 continue;
4141 id = pet_expr_access_get_id(stmt->args[param2pos[i]]);
4142 map = isl_map_set_dim_id(map, isl_dim_out, param2pos[i], id);
4143 map = isl_map_equate(map, isl_dim_param, i, isl_dim_out,
4144 param2pos[i]);
4145 map = isl_map_project_out(map, isl_dim_param, i, 1);
4148 stmt->domain = isl_map_wrap(map);
4150 space = isl_space_unwrap(isl_set_get_space(stmt->domain));
4151 space = isl_space_from_domain(isl_space_domain(space));
4152 ma = isl_multi_aff_zero(space);
4153 for (int pos = 0; pos < n; ++pos)
4154 stmt->args[pos] = embed(stmt->args[pos], ma);
4155 isl_multi_aff_free(ma);
4157 stmt = remove_nested_parameters(stmt);
4158 stmt = remove_duplicate_arguments(stmt, n);
4160 return stmt;
4163 /* For each statement in "scop", move the parameters that correspond
4164 * to nested access into the ranges of the domains and create
4165 * corresponding argument expressions.
4167 struct pet_scop *PetScan::resolve_nested(struct pet_scop *scop)
4169 if (!scop)
4170 return NULL;
4172 for (int i = 0; i < scop->n_stmt; ++i) {
4173 scop->stmts[i] = resolve_nested(scop->stmts[i]);
4174 if (!scop->stmts[i])
4175 goto error;
4178 return scop;
4179 error:
4180 pet_scop_free(scop);
4181 return NULL;
4184 /* Given an access expression "expr", is the variable accessed by
4185 * "expr" assigned anywhere inside "scop"?
4187 static bool is_assigned(pet_expr *expr, pet_scop *scop)
4189 bool assigned = false;
4190 isl_id *id;
4192 id = pet_expr_access_get_id(expr);
4193 assigned = pet_scop_writes(scop, id);
4194 isl_id_free(id);
4196 return assigned;
4199 /* Are all nested access parameters in "pa" allowed given "scop".
4200 * In particular, is none of them written by anywhere inside "scop".
4202 * If "scop" has any skip conditions, then no nested access parameters
4203 * are allowed. In particular, if there is any nested access in a guard
4204 * for a piece of code containing a "continue", then we want to introduce
4205 * a separate statement for evaluating this guard so that we can express
4206 * that the result is false for all previous iterations.
4208 bool PetScan::is_nested_allowed(__isl_keep isl_pw_aff *pa, pet_scop *scop)
4210 int nparam;
4212 if (!scop)
4213 return true;
4215 nparam = isl_pw_aff_dim(pa, isl_dim_param);
4216 for (int i = 0; i < nparam; ++i) {
4217 Expr *nested;
4218 isl_id *id = isl_pw_aff_get_dim_id(pa, isl_dim_param, i);
4219 pet_expr *expr;
4220 bool allowed;
4222 if (!is_nested_parameter(id)) {
4223 isl_id_free(id);
4224 continue;
4227 if (pet_scop_has_skip(scop, pet_skip_now)) {
4228 isl_id_free(id);
4229 return false;
4232 nested = (Expr *) isl_id_get_user(id);
4233 expr = extract_expr(nested);
4234 allowed = expr && expr->type == pet_expr_access &&
4235 !is_assigned(expr, scop);
4237 pet_expr_free(expr);
4238 isl_id_free(id);
4240 if (!allowed)
4241 return false;
4244 return true;
4247 /* Do we need to construct a skip condition of the given type
4248 * on an if statement, given that the if condition is non-affine?
4250 * pet_scop_filter_skip can only handle the case where the if condition
4251 * holds (the then branch) and the skip condition is universal.
4252 * In any other case, we need to construct a new skip condition.
4254 static bool need_skip(struct pet_scop *scop_then, struct pet_scop *scop_else,
4255 bool have_else, enum pet_skip type)
4257 if (have_else && scop_else && pet_scop_has_skip(scop_else, type))
4258 return true;
4259 if (scop_then && pet_scop_has_skip(scop_then, type) &&
4260 !pet_scop_has_universal_skip(scop_then, type))
4261 return true;
4262 return false;
4265 /* Do we need to construct a skip condition of the given type
4266 * on an if statement, given that the if condition is affine?
4268 * There is no need to construct a new skip condition if all
4269 * the skip conditions are affine.
4271 static bool need_skip_aff(struct pet_scop *scop_then,
4272 struct pet_scop *scop_else, bool have_else, enum pet_skip type)
4274 if (scop_then && pet_scop_has_var_skip(scop_then, type))
4275 return true;
4276 if (have_else && scop_else && pet_scop_has_var_skip(scop_else, type))
4277 return true;
4278 return false;
4281 /* Do we need to construct a skip condition of the given type
4282 * on an if statement?
4284 static bool need_skip(struct pet_scop *scop_then, struct pet_scop *scop_else,
4285 bool have_else, enum pet_skip type, bool affine)
4287 if (affine)
4288 return need_skip_aff(scop_then, scop_else, have_else, type);
4289 else
4290 return need_skip(scop_then, scop_else, have_else, type);
4293 /* Construct an affine expression pet_expr that evaluates
4294 * to the constant "val".
4296 static struct pet_expr *universally(isl_ctx *ctx, int val)
4298 isl_local_space *ls;
4299 isl_aff *aff;
4300 isl_multi_pw_aff *mpa;
4302 ls = isl_local_space_from_space(isl_space_set_alloc(ctx, 0, 0));
4303 aff = isl_aff_val_on_domain(ls, isl_val_int_from_si(ctx, val));
4304 mpa = isl_multi_pw_aff_from_pw_aff(isl_pw_aff_from_aff(aff));
4306 return pet_expr_from_index(mpa);
4309 /* Construct an affine expression pet_expr that evaluates
4310 * to the constant 1.
4312 static struct pet_expr *universally_true(isl_ctx *ctx)
4314 return universally(ctx, 1);
4317 /* Construct an affine expression pet_expr that evaluates
4318 * to the constant 0.
4320 static struct pet_expr *universally_false(isl_ctx *ctx)
4322 return universally(ctx, 0);
4325 /* Given an index expression "test_index" for the if condition,
4326 * an index expression "skip_index" for the skip condition and
4327 * scops for the then and else branches, construct a scop for
4328 * computing "skip_index".
4330 * The computed scop contains a single statement that essentially does
4332 * skip_index = test_cond ? skip_cond_then : skip_cond_else
4334 * If the skip conditions of the then and/or else branch are not affine,
4335 * then they need to be filtered by test_index.
4336 * If they are missing, then this means the skip condition is false.
4338 * Since we are constructing a skip condition for the if statement,
4339 * the skip conditions on the then and else branches are removed.
4341 static struct pet_scop *extract_skip(PetScan *scan,
4342 __isl_take isl_multi_pw_aff *test_index,
4343 __isl_take isl_multi_pw_aff *skip_index,
4344 struct pet_scop *scop_then, struct pet_scop *scop_else, bool have_else,
4345 enum pet_skip type)
4347 struct pet_expr *expr_then, *expr_else, *expr, *expr_skip;
4348 struct pet_stmt *stmt;
4349 struct pet_scop *scop;
4350 isl_ctx *ctx = scan->ctx;
4352 if (!scop_then)
4353 goto error;
4354 if (have_else && !scop_else)
4355 goto error;
4357 if (pet_scop_has_skip(scop_then, type)) {
4358 expr_then = pet_scop_get_skip_expr(scop_then, type);
4359 pet_scop_reset_skip(scop_then, type);
4360 if (!pet_expr_is_affine(expr_then))
4361 expr_then = pet_expr_filter(expr_then,
4362 isl_multi_pw_aff_copy(test_index), 1);
4363 } else
4364 expr_then = universally_false(ctx);
4366 if (have_else && pet_scop_has_skip(scop_else, type)) {
4367 expr_else = pet_scop_get_skip_expr(scop_else, type);
4368 pet_scop_reset_skip(scop_else, type);
4369 if (!pet_expr_is_affine(expr_else))
4370 expr_else = pet_expr_filter(expr_else,
4371 isl_multi_pw_aff_copy(test_index), 0);
4372 } else
4373 expr_else = universally_false(ctx);
4375 expr = pet_expr_from_index(test_index);
4376 expr = pet_expr_new_ternary(ctx, expr, expr_then, expr_else);
4377 expr_skip = pet_expr_from_index(isl_multi_pw_aff_copy(skip_index));
4378 if (expr_skip) {
4379 expr_skip->acc.write = 1;
4380 expr_skip->acc.read = 0;
4382 expr = pet_expr_new_binary(ctx, pet_op_assign, expr_skip, expr);
4383 stmt = pet_stmt_from_pet_expr(ctx, -1, NULL, scan->n_stmt++, expr);
4385 scop = pet_scop_from_pet_stmt(ctx, stmt);
4386 scop = scop_add_array(scop, skip_index, scan->ast_context);
4387 isl_multi_pw_aff_free(skip_index);
4389 return scop;
4390 error:
4391 isl_multi_pw_aff_free(test_index);
4392 isl_multi_pw_aff_free(skip_index);
4393 return NULL;
4396 /* Is scop's skip_now condition equal to its skip_later condition?
4397 * In particular, this means that it either has no skip_now condition
4398 * or both a skip_now and a skip_later condition (that are equal to each other).
4400 static bool skip_equals_skip_later(struct pet_scop *scop)
4402 int has_skip_now, has_skip_later;
4403 int equal;
4404 isl_multi_pw_aff *skip_now, *skip_later;
4406 if (!scop)
4407 return false;
4408 has_skip_now = pet_scop_has_skip(scop, pet_skip_now);
4409 has_skip_later = pet_scop_has_skip(scop, pet_skip_later);
4410 if (has_skip_now != has_skip_later)
4411 return false;
4412 if (!has_skip_now)
4413 return true;
4415 skip_now = pet_scop_get_skip(scop, pet_skip_now);
4416 skip_later = pet_scop_get_skip(scop, pet_skip_later);
4417 equal = isl_multi_pw_aff_is_equal(skip_now, skip_later);
4418 isl_multi_pw_aff_free(skip_now);
4419 isl_multi_pw_aff_free(skip_later);
4421 return equal;
4424 /* Drop the skip conditions of type pet_skip_later from scop1 and scop2.
4426 static void drop_skip_later(struct pet_scop *scop1, struct pet_scop *scop2)
4428 pet_scop_reset_skip(scop1, pet_skip_later);
4429 pet_scop_reset_skip(scop2, pet_skip_later);
4432 /* Structure that handles the construction of skip conditions.
4434 * scop_then and scop_else represent the then and else branches
4435 * of the if statement
4437 * skip[type] is true if we need to construct a skip condition of that type
4438 * equal is set if the skip conditions of types pet_skip_now and pet_skip_later
4439 * are equal to each other
4440 * index[type] is an index expression from a zero-dimension domain
4441 * to the virtual array representing the skip condition
4442 * scop[type] is a scop for computing the skip condition
4444 struct pet_skip_info {
4445 isl_ctx *ctx;
4447 bool skip[2];
4448 bool equal;
4449 isl_multi_pw_aff *index[2];
4450 struct pet_scop *scop[2];
4452 pet_skip_info(isl_ctx *ctx) : ctx(ctx) {}
4454 operator bool() { return skip[pet_skip_now] || skip[pet_skip_later]; }
4457 /* Structure that handles the construction of skip conditions on if statements.
4459 * scop_then and scop_else represent the then and else branches
4460 * of the if statement
4462 struct pet_skip_info_if : public pet_skip_info {
4463 struct pet_scop *scop_then, *scop_else;
4464 bool have_else;
4466 pet_skip_info_if(isl_ctx *ctx, struct pet_scop *scop_then,
4467 struct pet_scop *scop_else, bool have_else, bool affine);
4468 void extract(PetScan *scan, __isl_keep isl_multi_pw_aff *index,
4469 enum pet_skip type);
4470 void extract(PetScan *scan, __isl_keep isl_multi_pw_aff *index);
4471 void extract(PetScan *scan, __isl_keep isl_pw_aff *cond);
4472 struct pet_scop *add(struct pet_scop *scop, enum pet_skip type,
4473 int offset);
4474 struct pet_scop *add(struct pet_scop *scop, int offset);
4477 /* Initialize a pet_skip_info_if structure based on the then and else branches
4478 * and based on whether the if condition is affine or not.
4480 pet_skip_info_if::pet_skip_info_if(isl_ctx *ctx, struct pet_scop *scop_then,
4481 struct pet_scop *scop_else, bool have_else, bool affine) :
4482 pet_skip_info(ctx), scop_then(scop_then), scop_else(scop_else),
4483 have_else(have_else)
4485 skip[pet_skip_now] =
4486 need_skip(scop_then, scop_else, have_else, pet_skip_now, affine);
4487 equal = skip[pet_skip_now] && skip_equals_skip_later(scop_then) &&
4488 (!have_else || skip_equals_skip_later(scop_else));
4489 skip[pet_skip_later] = skip[pet_skip_now] && !equal &&
4490 need_skip(scop_then, scop_else, have_else, pet_skip_later, affine);
4493 /* If we need to construct a skip condition of the given type,
4494 * then do so now.
4496 * "mpa" represents the if condition.
4498 void pet_skip_info_if::extract(PetScan *scan,
4499 __isl_keep isl_multi_pw_aff *mpa, enum pet_skip type)
4501 isl_ctx *ctx;
4503 if (!skip[type])
4504 return;
4506 ctx = isl_multi_pw_aff_get_ctx(mpa);
4507 index[type] = create_test_index(ctx, scan->n_test++);
4508 scop[type] = extract_skip(scan, isl_multi_pw_aff_copy(mpa),
4509 isl_multi_pw_aff_copy(index[type]),
4510 scop_then, scop_else, have_else, type);
4513 /* Construct the required skip conditions, given the if condition "index".
4515 void pet_skip_info_if::extract(PetScan *scan,
4516 __isl_keep isl_multi_pw_aff *index)
4518 extract(scan, index, pet_skip_now);
4519 extract(scan, index, pet_skip_later);
4520 if (equal)
4521 drop_skip_later(scop_then, scop_else);
4524 /* Construct the required skip conditions, given the if condition "cond".
4526 void pet_skip_info_if::extract(PetScan *scan, __isl_keep isl_pw_aff *cond)
4528 isl_multi_pw_aff *test;
4530 if (!skip[pet_skip_now] && !skip[pet_skip_later])
4531 return;
4533 test = isl_multi_pw_aff_from_pw_aff(isl_pw_aff_copy(cond));
4534 test = isl_multi_pw_aff_from_range(test);
4535 extract(scan, test);
4536 isl_multi_pw_aff_free(test);
4539 /* Add the computed skip condition of the give type to "main" and
4540 * add the scop for computing the condition at the given offset.
4542 * If equal is set, then we only computed a skip condition for pet_skip_now,
4543 * but we also need to set it as main's pet_skip_later.
4545 struct pet_scop *pet_skip_info_if::add(struct pet_scop *main,
4546 enum pet_skip type, int offset)
4548 if (!skip[type])
4549 return main;
4551 scop[type] = pet_scop_prefix(scop[type], offset);
4552 main = pet_scop_add_par(ctx, main, scop[type]);
4553 scop[type] = NULL;
4555 if (equal)
4556 main = pet_scop_set_skip(main, pet_skip_later,
4557 isl_multi_pw_aff_copy(index[type]));
4559 main = pet_scop_set_skip(main, type, index[type]);
4560 index[type] = NULL;
4562 return main;
4565 /* Add the computed skip conditions to "main" and
4566 * add the scops for computing the conditions at the given offset.
4568 struct pet_scop *pet_skip_info_if::add(struct pet_scop *scop, int offset)
4570 scop = add(scop, pet_skip_now, offset);
4571 scop = add(scop, pet_skip_later, offset);
4573 return scop;
4576 /* Construct a pet_scop for a non-affine if statement.
4578 * We create a separate statement that writes the result
4579 * of the non-affine condition to a virtual scalar.
4580 * A constraint requiring the value of this virtual scalar to be one
4581 * is added to the iteration domains of the then branch.
4582 * Similarly, a constraint requiring the value of this virtual scalar
4583 * to be zero is added to the iteration domains of the else branch, if any.
4584 * We adjust the schedules to ensure that the virtual scalar is written
4585 * before it is read.
4587 * If there are any breaks or continues in the then and/or else
4588 * branches, then we may have to compute a new skip condition.
4589 * This is handled using a pet_skip_info_if object.
4590 * On initialization, the object checks if skip conditions need
4591 * to be computed. If so, it does so in "extract" and adds them in "add".
4593 struct pet_scop *PetScan::extract_non_affine_if(Expr *cond,
4594 struct pet_scop *scop_then, struct pet_scop *scop_else,
4595 bool have_else, int stmt_id)
4597 struct pet_scop *scop;
4598 isl_multi_pw_aff *test_index;
4599 int save_n_stmt = n_stmt;
4601 test_index = create_test_index(ctx, n_test++);
4602 n_stmt = stmt_id;
4603 scop = extract_non_affine_condition(cond, n_stmt++,
4604 isl_multi_pw_aff_copy(test_index));
4605 n_stmt = save_n_stmt;
4606 scop = scop_add_array(scop, test_index, ast_context);
4608 pet_skip_info_if skip(ctx, scop_then, scop_else, have_else, false);
4609 skip.extract(this, test_index);
4611 scop = pet_scop_prefix(scop, 0);
4612 scop_then = pet_scop_prefix(scop_then, 1);
4613 scop_then = pet_scop_filter(scop_then,
4614 isl_multi_pw_aff_copy(test_index), 1);
4615 if (have_else) {
4616 scop_else = pet_scop_prefix(scop_else, 1);
4617 scop_else = pet_scop_filter(scop_else, test_index, 0);
4618 scop_then = pet_scop_add_par(ctx, scop_then, scop_else);
4619 } else
4620 isl_multi_pw_aff_free(test_index);
4622 scop = pet_scop_add_seq(ctx, scop, scop_then);
4624 scop = skip.add(scop, 2);
4626 return scop;
4629 /* Construct a pet_scop for an if statement.
4631 * If the condition fits the pattern of a conditional assignment,
4632 * then it is handled by extract_conditional_assignment.
4633 * Otherwise, we do the following.
4635 * If the condition is affine, then the condition is added
4636 * to the iteration domains of the then branch, while the
4637 * opposite of the condition in added to the iteration domains
4638 * of the else branch, if any.
4639 * We allow the condition to be dynamic, i.e., to refer to
4640 * scalars or array elements that may be written to outside
4641 * of the given if statement. These nested accesses are then represented
4642 * as output dimensions in the wrapping iteration domain.
4643 * If it also written _inside_ the then or else branch, then
4644 * we treat the condition as non-affine.
4645 * As explained in extract_non_affine_if, this will introduce
4646 * an extra statement.
4647 * For aesthetic reasons, we want this statement to have a statement
4648 * number that is lower than those of the then and else branches.
4649 * In order to evaluate if will need such a statement, however, we
4650 * first construct scops for the then and else branches.
4651 * We therefore reserve a statement number if we might have to
4652 * introduce such an extra statement.
4654 * If the condition is not affine, then the scop is created in
4655 * extract_non_affine_if.
4657 * If there are any breaks or continues in the then and/or else
4658 * branches, then we may have to compute a new skip condition.
4659 * This is handled using a pet_skip_info_if object.
4660 * On initialization, the object checks if skip conditions need
4661 * to be computed. If so, it does so in "extract" and adds them in "add".
4663 struct pet_scop *PetScan::extract(IfStmt *stmt)
4665 struct pet_scop *scop_then, *scop_else = NULL, *scop;
4666 isl_pw_aff *cond;
4667 int stmt_id;
4668 isl_set *set;
4669 isl_set *valid;
4671 clear_assignments clear(assigned_value);
4672 clear.TraverseStmt(stmt->getThen());
4673 if (stmt->getElse())
4674 clear.TraverseStmt(stmt->getElse());
4676 scop = extract_conditional_assignment(stmt);
4677 if (scop)
4678 return scop;
4680 cond = try_extract_nested_condition(stmt->getCond());
4681 if (allow_nested && (!cond || has_nested(cond)))
4682 stmt_id = n_stmt++;
4685 assigned_value_cache cache(assigned_value);
4686 scop_then = extract(stmt->getThen());
4689 if (stmt->getElse()) {
4690 assigned_value_cache cache(assigned_value);
4691 scop_else = extract(stmt->getElse());
4692 if (options->autodetect) {
4693 if (scop_then && !scop_else) {
4694 partial = true;
4695 isl_pw_aff_free(cond);
4696 return scop_then;
4698 if (!scop_then && scop_else) {
4699 partial = true;
4700 isl_pw_aff_free(cond);
4701 return scop_else;
4706 if (cond &&
4707 (!is_nested_allowed(cond, scop_then) ||
4708 (stmt->getElse() && !is_nested_allowed(cond, scop_else)))) {
4709 isl_pw_aff_free(cond);
4710 cond = NULL;
4712 if (allow_nested && !cond)
4713 return extract_non_affine_if(stmt->getCond(), scop_then,
4714 scop_else, stmt->getElse(), stmt_id);
4716 if (!cond)
4717 cond = extract_condition(stmt->getCond());
4719 pet_skip_info_if skip(ctx, scop_then, scop_else, stmt->getElse(), true);
4720 skip.extract(this, cond);
4722 valid = isl_pw_aff_domain(isl_pw_aff_copy(cond));
4723 set = isl_pw_aff_non_zero_set(cond);
4724 scop = pet_scop_restrict(scop_then, isl_set_copy(set));
4726 if (stmt->getElse()) {
4727 set = isl_set_subtract(isl_set_copy(valid), set);
4728 scop_else = pet_scop_restrict(scop_else, set);
4729 scop = pet_scop_add_par(ctx, scop, scop_else);
4730 } else
4731 isl_set_free(set);
4732 scop = resolve_nested(scop);
4733 scop = pet_scop_restrict_context(scop, valid);
4735 if (skip)
4736 scop = pet_scop_prefix(scop, 0);
4737 scop = skip.add(scop, 1);
4739 return scop;
4742 /* Try and construct a pet_scop for a label statement.
4743 * We currently only allow labels on expression statements.
4745 struct pet_scop *PetScan::extract(LabelStmt *stmt)
4747 isl_id *label;
4748 Stmt *sub;
4750 sub = stmt->getSubStmt();
4751 if (!isa<Expr>(sub)) {
4752 unsupported(stmt);
4753 return NULL;
4756 label = isl_id_alloc(ctx, stmt->getName(), NULL);
4758 return extract(sub, extract_expr(cast<Expr>(sub)), label);
4761 /* Return a one-dimensional multi piecewise affine expression that is equal
4762 * to the constant 1 and is defined over a zero-dimensional domain.
4764 static __isl_give isl_multi_pw_aff *one_mpa(isl_ctx *ctx)
4766 isl_space *space;
4767 isl_local_space *ls;
4768 isl_aff *aff;
4770 space = isl_space_set_alloc(ctx, 0, 0);
4771 ls = isl_local_space_from_space(space);
4772 aff = isl_aff_zero_on_domain(ls);
4773 aff = isl_aff_set_constant_si(aff, 1);
4775 return isl_multi_pw_aff_from_pw_aff(isl_pw_aff_from_aff(aff));
4778 /* Construct a pet_scop for a continue statement.
4780 * We simply create an empty scop with a universal pet_skip_now
4781 * skip condition. This skip condition will then be taken into
4782 * account by the enclosing loop construct, possibly after
4783 * being incorporated into outer skip conditions.
4785 struct pet_scop *PetScan::extract(ContinueStmt *stmt)
4787 pet_scop *scop;
4789 scop = pet_scop_empty(ctx);
4790 if (!scop)
4791 return NULL;
4793 scop = pet_scop_set_skip(scop, pet_skip_now, one_mpa(ctx));
4795 return scop;
4798 /* Construct a pet_scop for a break statement.
4800 * We simply create an empty scop with both a universal pet_skip_now
4801 * skip condition and a universal pet_skip_later skip condition.
4802 * These skip conditions will then be taken into
4803 * account by the enclosing loop construct, possibly after
4804 * being incorporated into outer skip conditions.
4806 struct pet_scop *PetScan::extract(BreakStmt *stmt)
4808 pet_scop *scop;
4809 isl_multi_pw_aff *skip;
4811 scop = pet_scop_empty(ctx);
4812 if (!scop)
4813 return NULL;
4815 skip = one_mpa(ctx);
4816 scop = pet_scop_set_skip(scop, pet_skip_now,
4817 isl_multi_pw_aff_copy(skip));
4818 scop = pet_scop_set_skip(scop, pet_skip_later, skip);
4820 return scop;
4823 /* Try and construct a pet_scop corresponding to "stmt".
4825 * If "stmt" is a compound statement, then "skip_declarations"
4826 * indicates whether we should skip initial declarations in the
4827 * compound statement.
4829 * If the constructed pet_scop is not a (possibly) partial representation
4830 * of "stmt", we update start and end of the pet_scop to those of "stmt".
4831 * In particular, if skip_declarations, then we may have skipped declarations
4832 * inside "stmt" and so the pet_scop may not represent the entire "stmt".
4833 * Note that this function may be called with "stmt" referring to the entire
4834 * body of the function, including the outer braces. In such cases,
4835 * skip_declarations will be set and the braces will not be taken into
4836 * account in scop->start and scop->end.
4838 struct pet_scop *PetScan::extract(Stmt *stmt, bool skip_declarations)
4840 struct pet_scop *scop;
4842 if (isa<Expr>(stmt))
4843 return extract(stmt, extract_expr(cast<Expr>(stmt)));
4845 switch (stmt->getStmtClass()) {
4846 case Stmt::WhileStmtClass:
4847 scop = extract(cast<WhileStmt>(stmt));
4848 break;
4849 case Stmt::ForStmtClass:
4850 scop = extract_for(cast<ForStmt>(stmt));
4851 break;
4852 case Stmt::IfStmtClass:
4853 scop = extract(cast<IfStmt>(stmt));
4854 break;
4855 case Stmt::CompoundStmtClass:
4856 scop = extract(cast<CompoundStmt>(stmt), skip_declarations);
4857 break;
4858 case Stmt::LabelStmtClass:
4859 scop = extract(cast<LabelStmt>(stmt));
4860 break;
4861 case Stmt::ContinueStmtClass:
4862 scop = extract(cast<ContinueStmt>(stmt));
4863 break;
4864 case Stmt::BreakStmtClass:
4865 scop = extract(cast<BreakStmt>(stmt));
4866 break;
4867 case Stmt::DeclStmtClass:
4868 scop = extract(cast<DeclStmt>(stmt));
4869 break;
4870 default:
4871 unsupported(stmt);
4872 return NULL;
4875 if (partial || skip_declarations)
4876 return scop;
4878 scop = update_scop_start_end(scop, stmt->getSourceRange(), false);
4880 return scop;
4883 /* Do we need to construct a skip condition of the given type
4884 * on a sequence of statements?
4886 * There is no need to construct a new skip condition if only
4887 * only of the two statements has a skip condition or if both
4888 * of their skip conditions are affine.
4890 * In principle we also don't need a new continuation variable if
4891 * the continuation of scop2 is affine, but then we would need
4892 * to allow more complicated forms of continuations.
4894 static bool need_skip_seq(struct pet_scop *scop1, struct pet_scop *scop2,
4895 enum pet_skip type)
4897 if (!scop1 || !pet_scop_has_skip(scop1, type))
4898 return false;
4899 if (!scop2 || !pet_scop_has_skip(scop2, type))
4900 return false;
4901 if (pet_scop_has_affine_skip(scop1, type) &&
4902 pet_scop_has_affine_skip(scop2, type))
4903 return false;
4904 return true;
4907 /* Construct a scop for computing the skip condition of the given type and
4908 * with index expression "skip_index" for a sequence of two scops "scop1"
4909 * and "scop2".
4911 * The computed scop contains a single statement that essentially does
4913 * skip_index = skip_cond_1 ? 1 : skip_cond_2
4915 * or, in other words, skip_cond1 || skip_cond2.
4916 * In this expression, skip_cond_2 is filtered to reflect that it is
4917 * only evaluated when skip_cond_1 is false.
4919 * The skip condition on scop1 is not removed because it still needs
4920 * to be applied to scop2 when these two scops are combined.
4922 static struct pet_scop *extract_skip_seq(PetScan *ps,
4923 __isl_take isl_multi_pw_aff *skip_index,
4924 struct pet_scop *scop1, struct pet_scop *scop2, enum pet_skip type)
4926 struct pet_expr *expr1, *expr2, *expr, *expr_skip;
4927 struct pet_stmt *stmt;
4928 struct pet_scop *scop;
4929 isl_ctx *ctx = ps->ctx;
4931 if (!scop1 || !scop2)
4932 goto error;
4934 expr1 = pet_scop_get_skip_expr(scop1, type);
4935 expr2 = pet_scop_get_skip_expr(scop2, type);
4936 pet_scop_reset_skip(scop2, type);
4938 expr2 = pet_expr_filter(expr2,
4939 isl_multi_pw_aff_copy(expr1->acc.index), 0);
4941 expr = universally_true(ctx);
4942 expr = pet_expr_new_ternary(ctx, expr1, expr, expr2);
4943 expr_skip = pet_expr_from_index(isl_multi_pw_aff_copy(skip_index));
4944 if (expr_skip) {
4945 expr_skip->acc.write = 1;
4946 expr_skip->acc.read = 0;
4948 expr = pet_expr_new_binary(ctx, pet_op_assign, expr_skip, expr);
4949 stmt = pet_stmt_from_pet_expr(ctx, -1, NULL, ps->n_stmt++, expr);
4951 scop = pet_scop_from_pet_stmt(ctx, stmt);
4952 scop = scop_add_array(scop, skip_index, ps->ast_context);
4953 isl_multi_pw_aff_free(skip_index);
4955 return scop;
4956 error:
4957 isl_multi_pw_aff_free(skip_index);
4958 return NULL;
4961 /* Structure that handles the construction of skip conditions
4962 * on sequences of statements.
4964 * scop1 and scop2 represent the two statements that are combined
4966 struct pet_skip_info_seq : public pet_skip_info {
4967 struct pet_scop *scop1, *scop2;
4969 pet_skip_info_seq(isl_ctx *ctx, struct pet_scop *scop1,
4970 struct pet_scop *scop2);
4971 void extract(PetScan *scan, enum pet_skip type);
4972 void extract(PetScan *scan);
4973 struct pet_scop *add(struct pet_scop *scop, enum pet_skip type,
4974 int offset);
4975 struct pet_scop *add(struct pet_scop *scop, int offset);
4978 /* Initialize a pet_skip_info_seq structure based on
4979 * on the two statements that are going to be combined.
4981 pet_skip_info_seq::pet_skip_info_seq(isl_ctx *ctx, struct pet_scop *scop1,
4982 struct pet_scop *scop2) : pet_skip_info(ctx), scop1(scop1), scop2(scop2)
4984 skip[pet_skip_now] = need_skip_seq(scop1, scop2, pet_skip_now);
4985 equal = skip[pet_skip_now] && skip_equals_skip_later(scop1) &&
4986 skip_equals_skip_later(scop2);
4987 skip[pet_skip_later] = skip[pet_skip_now] && !equal &&
4988 need_skip_seq(scop1, scop2, pet_skip_later);
4991 /* If we need to construct a skip condition of the given type,
4992 * then do so now.
4994 void pet_skip_info_seq::extract(PetScan *scan, enum pet_skip type)
4996 if (!skip[type])
4997 return;
4999 index[type] = create_test_index(ctx, scan->n_test++);
5000 scop[type] = extract_skip_seq(scan, isl_multi_pw_aff_copy(index[type]),
5001 scop1, scop2, type);
5004 /* Construct the required skip conditions.
5006 void pet_skip_info_seq::extract(PetScan *scan)
5008 extract(scan, pet_skip_now);
5009 extract(scan, pet_skip_later);
5010 if (equal)
5011 drop_skip_later(scop1, scop2);
5014 /* Add the computed skip condition of the given type to "main" and
5015 * add the scop for computing the condition at the given offset (the statement
5016 * number). Within this offset, the condition is computed at position 1
5017 * to ensure that it is computed after the corresponding statement.
5019 * If equal is set, then we only computed a skip condition for pet_skip_now,
5020 * but we also need to set it as main's pet_skip_later.
5022 struct pet_scop *pet_skip_info_seq::add(struct pet_scop *main,
5023 enum pet_skip type, int offset)
5025 if (!skip[type])
5026 return main;
5028 scop[type] = pet_scop_prefix(scop[type], 1);
5029 scop[type] = pet_scop_prefix(scop[type], offset);
5030 main = pet_scop_add_par(ctx, main, scop[type]);
5031 scop[type] = NULL;
5033 if (equal)
5034 main = pet_scop_set_skip(main, pet_skip_later,
5035 isl_multi_pw_aff_copy(index[type]));
5037 main = pet_scop_set_skip(main, type, index[type]);
5038 index[type] = NULL;
5040 return main;
5043 /* Add the computed skip conditions to "main" and
5044 * add the scops for computing the conditions at the given offset.
5046 struct pet_scop *pet_skip_info_seq::add(struct pet_scop *scop, int offset)
5048 scop = add(scop, pet_skip_now, offset);
5049 scop = add(scop, pet_skip_later, offset);
5051 return scop;
5054 /* Extract a clone of the kill statement in "scop".
5055 * "scop" is expected to have been created from a DeclStmt
5056 * and should have the kill as its first statement.
5058 struct pet_stmt *PetScan::extract_kill(struct pet_scop *scop)
5060 struct pet_expr *kill;
5061 struct pet_stmt *stmt;
5062 isl_multi_pw_aff *index;
5063 isl_map *access;
5065 if (!scop)
5066 return NULL;
5067 if (scop->n_stmt < 1)
5068 isl_die(ctx, isl_error_internal,
5069 "expecting at least one statement", return NULL);
5070 stmt = scop->stmts[0];
5071 if (stmt->body->type != pet_expr_unary ||
5072 stmt->body->op != pet_op_kill)
5073 isl_die(ctx, isl_error_internal,
5074 "expecting kill statement", return NULL);
5076 index = isl_multi_pw_aff_copy(stmt->body->args[0]->acc.index);
5077 access = isl_map_copy(stmt->body->args[0]->acc.access);
5078 index = isl_multi_pw_aff_reset_tuple_id(index, isl_dim_in);
5079 access = isl_map_reset_tuple_id(access, isl_dim_in);
5080 kill = pet_expr_kill_from_access_and_index(access, index);
5081 return pet_stmt_from_pet_expr(ctx, stmt->line, NULL, n_stmt++, kill);
5084 /* Mark all arrays in "scop" as being exposed.
5086 static struct pet_scop *mark_exposed(struct pet_scop *scop)
5088 if (!scop)
5089 return NULL;
5090 for (int i = 0; i < scop->n_array; ++i)
5091 scop->arrays[i]->exposed = 1;
5092 return scop;
5095 /* Try and construct a pet_scop corresponding to (part of)
5096 * a sequence of statements.
5098 * "block" is set if the sequence respresents the children of
5099 * a compound statement.
5100 * "skip_declarations" is set if we should skip initial declarations
5101 * in the sequence of statements.
5103 * If there are any breaks or continues in the individual statements,
5104 * then we may have to compute a new skip condition.
5105 * This is handled using a pet_skip_info_seq object.
5106 * On initialization, the object checks if skip conditions need
5107 * to be computed. If so, it does so in "extract" and adds them in "add".
5109 * If "block" is set, then we need to insert kill statements at
5110 * the end of the block for any array that has been declared by
5111 * one of the statements in the sequence. Each of these declarations
5112 * results in the construction of a kill statement at the place
5113 * of the declaration, so we simply collect duplicates of
5114 * those kill statements and append these duplicates to the constructed scop.
5116 * If "block" is not set, then any array declared by one of the statements
5117 * in the sequence is marked as being exposed.
5119 * If autodetect is set, then we allow the extraction of only a subrange
5120 * of the sequence of statements. However, if there is at least one statement
5121 * for which we could not construct a scop and the final range contains
5122 * either no statements or at least one kill, then we discard the entire
5123 * range.
5125 struct pet_scop *PetScan::extract(StmtRange stmt_range, bool block,
5126 bool skip_declarations)
5128 pet_scop *scop;
5129 StmtIterator i;
5130 int j;
5131 bool partial_range = false;
5132 set<struct pet_stmt *> kills;
5133 set<struct pet_stmt *>::iterator it;
5135 scop = pet_scop_empty(ctx);
5136 for (i = stmt_range.first, j = 0; i != stmt_range.second; ++i, ++j) {
5137 Stmt *child = *i;
5138 struct pet_scop *scop_i;
5140 if (scop->n_stmt == 0 && skip_declarations &&
5141 child->getStmtClass() == Stmt::DeclStmtClass)
5142 continue;
5144 scop_i = extract(child);
5145 if (scop->n_stmt != 0 && partial) {
5146 pet_scop_free(scop_i);
5147 break;
5149 pet_skip_info_seq skip(ctx, scop, scop_i);
5150 skip.extract(this);
5151 if (skip)
5152 scop_i = pet_scop_prefix(scop_i, 0);
5153 if (scop_i && child->getStmtClass() == Stmt::DeclStmtClass) {
5154 if (block)
5155 kills.insert(extract_kill(scop_i));
5156 else
5157 scop_i = mark_exposed(scop_i);
5159 scop_i = pet_scop_prefix(scop_i, j);
5160 if (options->autodetect) {
5161 if (scop_i)
5162 scop = pet_scop_add_seq(ctx, scop, scop_i);
5163 else
5164 partial_range = true;
5165 if (scop->n_stmt != 0 && !scop_i)
5166 partial = true;
5167 } else {
5168 scop = pet_scop_add_seq(ctx, scop, scop_i);
5171 scop = skip.add(scop, j);
5173 if (partial || !scop)
5174 break;
5177 for (it = kills.begin(); it != kills.end(); ++it) {
5178 pet_scop *scop_j;
5179 scop_j = pet_scop_from_pet_stmt(ctx, *it);
5180 scop_j = pet_scop_prefix(scop_j, j);
5181 scop = pet_scop_add_seq(ctx, scop, scop_j);
5184 if (scop && partial_range) {
5185 if (scop->n_stmt == 0 || kills.size() != 0) {
5186 pet_scop_free(scop);
5187 return NULL;
5189 partial = true;
5192 return scop;
5195 /* Check if the scop marked by the user is exactly this Stmt
5196 * or part of this Stmt.
5197 * If so, return a pet_scop corresponding to the marked region.
5198 * Otherwise, return NULL.
5200 struct pet_scop *PetScan::scan(Stmt *stmt)
5202 SourceManager &SM = PP.getSourceManager();
5203 unsigned start_off, end_off;
5205 start_off = getExpansionOffset(SM, stmt->getLocStart());
5206 end_off = getExpansionOffset(SM, stmt->getLocEnd());
5208 if (start_off > loc.end)
5209 return NULL;
5210 if (end_off < loc.start)
5211 return NULL;
5212 if (start_off >= loc.start && end_off <= loc.end) {
5213 return extract(stmt);
5216 StmtIterator start;
5217 for (start = stmt->child_begin(); start != stmt->child_end(); ++start) {
5218 Stmt *child = *start;
5219 if (!child)
5220 continue;
5221 start_off = getExpansionOffset(SM, child->getLocStart());
5222 end_off = getExpansionOffset(SM, child->getLocEnd());
5223 if (start_off < loc.start && end_off >= loc.end)
5224 return scan(child);
5225 if (start_off >= loc.start)
5226 break;
5229 StmtIterator end;
5230 for (end = start; end != stmt->child_end(); ++end) {
5231 Stmt *child = *end;
5232 start_off = SM.getFileOffset(child->getLocStart());
5233 if (start_off >= loc.end)
5234 break;
5237 return extract(StmtRange(start, end), false, false);
5240 /* Set the size of index "pos" of "array" to "size".
5241 * In particular, add a constraint of the form
5243 * i_pos < size
5245 * to array->extent and a constraint of the form
5247 * size >= 0
5249 * to array->context.
5251 static struct pet_array *update_size(struct pet_array *array, int pos,
5252 __isl_take isl_pw_aff *size)
5254 isl_set *valid;
5255 isl_set *univ;
5256 isl_set *bound;
5257 isl_space *dim;
5258 isl_aff *aff;
5259 isl_pw_aff *index;
5260 isl_id *id;
5262 valid = isl_pw_aff_nonneg_set(isl_pw_aff_copy(size));
5263 array->context = isl_set_intersect(array->context, valid);
5265 dim = isl_set_get_space(array->extent);
5266 aff = isl_aff_zero_on_domain(isl_local_space_from_space(dim));
5267 aff = isl_aff_add_coefficient_si(aff, isl_dim_in, pos, 1);
5268 univ = isl_set_universe(isl_aff_get_domain_space(aff));
5269 index = isl_pw_aff_alloc(univ, aff);
5271 size = isl_pw_aff_add_dims(size, isl_dim_in,
5272 isl_set_dim(array->extent, isl_dim_set));
5273 id = isl_set_get_tuple_id(array->extent);
5274 size = isl_pw_aff_set_tuple_id(size, isl_dim_in, id);
5275 bound = isl_pw_aff_lt_set(index, size);
5277 array->extent = isl_set_intersect(array->extent, bound);
5279 if (!array->context || !array->extent)
5280 goto error;
5282 return array;
5283 error:
5284 pet_array_free(array);
5285 return NULL;
5288 /* Figure out the size of the array at position "pos" and all
5289 * subsequent positions from "type" and update "array" accordingly.
5291 struct pet_array *PetScan::set_upper_bounds(struct pet_array *array,
5292 const Type *type, int pos)
5294 const ArrayType *atype;
5295 isl_pw_aff *size;
5297 if (!array)
5298 return NULL;
5300 if (type->isPointerType()) {
5301 type = type->getPointeeType().getTypePtr();
5302 return set_upper_bounds(array, type, pos + 1);
5304 if (!type->isArrayType())
5305 return array;
5307 type = type->getCanonicalTypeInternal().getTypePtr();
5308 atype = cast<ArrayType>(type);
5310 if (type->isConstantArrayType()) {
5311 const ConstantArrayType *ca = cast<ConstantArrayType>(atype);
5312 size = extract_affine(ca->getSize());
5313 array = update_size(array, pos, size);
5314 } else if (type->isVariableArrayType()) {
5315 const VariableArrayType *vla = cast<VariableArrayType>(atype);
5316 size = extract_affine(vla->getSizeExpr());
5317 array = update_size(array, pos, size);
5320 type = atype->getElementType().getTypePtr();
5322 return set_upper_bounds(array, type, pos + 1);
5325 /* Is "T" the type of a variable length array with static size?
5327 static bool is_vla_with_static_size(QualType T)
5329 const VariableArrayType *vlatype;
5331 if (!T->isVariableArrayType())
5332 return false;
5333 vlatype = cast<VariableArrayType>(T);
5334 return vlatype->getSizeModifier() == VariableArrayType::Static;
5337 /* Return the type of "decl" as an array.
5339 * In particular, if "decl" is a parameter declaration that
5340 * is a variable length array with a static size, then
5341 * return the original type (i.e., the variable length array).
5342 * Otherwise, return the type of decl.
5344 static QualType get_array_type(ValueDecl *decl)
5346 ParmVarDecl *parm;
5347 QualType T;
5349 parm = dyn_cast<ParmVarDecl>(decl);
5350 if (!parm)
5351 return decl->getType();
5353 T = parm->getOriginalType();
5354 if (!is_vla_with_static_size(T))
5355 return decl->getType();
5356 return T;
5359 /* Does "decl" have definition that we can keep track of in a pet_type?
5361 static bool has_printable_definition(RecordDecl *decl)
5363 if (!decl->getDeclName())
5364 return false;
5365 return decl->getLexicalDeclContext() == decl->getDeclContext();
5368 /* Construct and return a pet_array corresponding to the variable "decl".
5369 * In particular, initialize array->extent to
5371 * { name[i_1,...,i_d] : i_1,...,i_d >= 0 }
5373 * and then call set_upper_bounds to set the upper bounds on the indices
5374 * based on the type of the variable.
5376 * If the base type is that of a record with a top-level definition and
5377 * if "types" is not null, then the RecordDecl corresponding to the type
5378 * is added to "types".
5380 * If the base type is that of a record with no top-level definition,
5381 * then we replace it by "<subfield>".
5383 struct pet_array *PetScan::extract_array(isl_ctx *ctx, ValueDecl *decl,
5384 lex_recorddecl_set *types)
5386 struct pet_array *array;
5387 QualType qt = get_array_type(decl);
5388 const Type *type = qt.getTypePtr();
5389 int depth = array_depth(type);
5390 QualType base = pet_clang_base_type(qt);
5391 string name;
5392 isl_id *id;
5393 isl_space *dim;
5395 array = isl_calloc_type(ctx, struct pet_array);
5396 if (!array)
5397 return NULL;
5399 id = isl_id_alloc(ctx, decl->getName().str().c_str(), decl);
5400 dim = isl_space_set_alloc(ctx, 0, depth);
5401 dim = isl_space_set_tuple_id(dim, isl_dim_set, id);
5403 array->extent = isl_set_nat_universe(dim);
5405 dim = isl_space_params_alloc(ctx, 0);
5406 array->context = isl_set_universe(dim);
5408 array = set_upper_bounds(array, type, 0);
5409 if (!array)
5410 return NULL;
5412 name = base.getAsString();
5414 if (types && base->isRecordType()) {
5415 RecordDecl *decl = pet_clang_record_decl(base);
5416 if (has_printable_definition(decl))
5417 types->insert(decl);
5418 else
5419 name = "<subfield>";
5422 array->element_type = strdup(name.c_str());
5423 array->element_is_record = base->isRecordType();
5424 array->element_size = decl->getASTContext().getTypeInfo(base).first / 8;
5426 return array;
5429 /* Construct and return a pet_array corresponding to the sequence
5430 * of declarations "decls".
5431 * If the sequence contains a single declaration, then it corresponds
5432 * to a simple array access. Otherwise, it corresponds to a member access,
5433 * with the declaration for the substructure following that of the containing
5434 * structure in the sequence of declarations.
5435 * We start with the outermost substructure and then combine it with
5436 * information from the inner structures.
5438 * Additionally, keep track of all required types in "types".
5440 struct pet_array *PetScan::extract_array(isl_ctx *ctx,
5441 vector<ValueDecl *> decls, lex_recorddecl_set *types)
5443 struct pet_array *array;
5444 vector<ValueDecl *>::iterator it;
5446 it = decls.begin();
5448 array = extract_array(ctx, *it, types);
5450 for (++it; it != decls.end(); ++it) {
5451 struct pet_array *parent;
5452 const char *base_name, *field_name;
5453 char *product_name;
5455 parent = array;
5456 array = extract_array(ctx, *it, types);
5457 if (!array)
5458 return pet_array_free(parent);
5460 base_name = isl_set_get_tuple_name(parent->extent);
5461 field_name = isl_set_get_tuple_name(array->extent);
5462 product_name = member_access_name(ctx, base_name, field_name);
5464 array->extent = isl_set_product(isl_set_copy(parent->extent),
5465 array->extent);
5466 if (product_name)
5467 array->extent = isl_set_set_tuple_name(array->extent,
5468 product_name);
5469 array->context = isl_set_intersect(array->context,
5470 isl_set_copy(parent->context));
5472 pet_array_free(parent);
5473 free(product_name);
5475 if (!array->extent || !array->context || !product_name)
5476 return pet_array_free(array);
5479 return array;
5482 /* Add a pet_type corresponding to "decl" to "scop, provided
5483 * it is a member of "types" and it has not been added before
5484 * (i.e., it is not a member of "types_done".
5486 * Since we want the user to be able to print the types
5487 * in the order in which they appear in the scop, we need to
5488 * make sure that types of fields in a structure appear before
5489 * that structure. We therefore call ourselves recursively
5490 * on the types of all record subfields.
5492 static struct pet_scop *add_type(isl_ctx *ctx, struct pet_scop *scop,
5493 RecordDecl *decl, Preprocessor &PP, lex_recorddecl_set &types,
5494 lex_recorddecl_set &types_done)
5496 string s;
5497 llvm::raw_string_ostream S(s);
5498 RecordDecl::field_iterator it;
5500 if (types.find(decl) == types.end())
5501 return scop;
5502 if (types_done.find(decl) != types_done.end())
5503 return scop;
5505 for (it = decl->field_begin(); it != decl->field_end(); ++it) {
5506 RecordDecl *record;
5507 QualType type = it->getType();
5509 if (!type->isRecordType())
5510 continue;
5511 record = pet_clang_record_decl(type);
5512 scop = add_type(ctx, scop, record, PP, types, types_done);
5515 if (strlen(decl->getName().str().c_str()) == 0)
5516 return scop;
5518 decl->print(S, PrintingPolicy(PP.getLangOpts()));
5519 S.str();
5521 scop->types[scop->n_type] = pet_type_alloc(ctx,
5522 decl->getName().str().c_str(), s.c_str());
5523 if (!scop->types[scop->n_type])
5524 return pet_scop_free(scop);
5526 types_done.insert(decl);
5528 scop->n_type++;
5530 return scop;
5533 /* Construct a list of pet_arrays, one for each array (or scalar)
5534 * accessed inside "scop", add this list to "scop" and return the result.
5536 * The context of "scop" is updated with the intersection of
5537 * the contexts of all arrays, i.e., constraints on the parameters
5538 * that ensure that the arrays have a valid (non-negative) size.
5540 * If the any of the extracted arrays refers to a member access,
5541 * then also add the required types to "scop".
5543 struct pet_scop *PetScan::scan_arrays(struct pet_scop *scop)
5545 int i;
5546 set<vector<ValueDecl *> > arrays;
5547 set<vector<ValueDecl *> >::iterator it;
5548 lex_recorddecl_set types;
5549 lex_recorddecl_set types_done;
5550 lex_recorddecl_set::iterator types_it;
5551 int n_array;
5552 struct pet_array **scop_arrays;
5554 if (!scop)
5555 return NULL;
5557 pet_scop_collect_arrays(scop, arrays);
5558 if (arrays.size() == 0)
5559 return scop;
5561 n_array = scop->n_array;
5563 scop_arrays = isl_realloc_array(ctx, scop->arrays, struct pet_array *,
5564 n_array + arrays.size());
5565 if (!scop_arrays)
5566 goto error;
5567 scop->arrays = scop_arrays;
5569 for (it = arrays.begin(), i = 0; it != arrays.end(); ++it, ++i) {
5570 struct pet_array *array;
5571 array = extract_array(ctx, *it, &types);
5572 scop->arrays[n_array + i] = array;
5573 if (!scop->arrays[n_array + i])
5574 goto error;
5575 scop->n_array++;
5576 scop->context = isl_set_intersect(scop->context,
5577 isl_set_copy(array->context));
5578 if (!scop->context)
5579 goto error;
5582 if (types.size() == 0)
5583 return scop;
5585 scop->types = isl_alloc_array(ctx, struct pet_type *, types.size());
5586 if (!scop->types)
5587 goto error;
5589 for (types_it = types.begin(); types_it != types.end(); ++types_it)
5590 scop = add_type(ctx, scop, *types_it, PP, types, types_done);
5592 return scop;
5593 error:
5594 pet_scop_free(scop);
5595 return NULL;
5598 /* Bound all parameters in scop->context to the possible values
5599 * of the corresponding C variable.
5601 static struct pet_scop *add_parameter_bounds(struct pet_scop *scop)
5603 int n;
5605 if (!scop)
5606 return NULL;
5608 n = isl_set_dim(scop->context, isl_dim_param);
5609 for (int i = 0; i < n; ++i) {
5610 isl_id *id;
5611 ValueDecl *decl;
5613 id = isl_set_get_dim_id(scop->context, isl_dim_param, i);
5614 if (is_nested_parameter(id)) {
5615 isl_id_free(id);
5616 isl_die(isl_set_get_ctx(scop->context),
5617 isl_error_internal,
5618 "unresolved nested parameter", goto error);
5620 decl = (ValueDecl *) isl_id_get_user(id);
5621 isl_id_free(id);
5623 scop->context = set_parameter_bounds(scop->context, i, decl);
5625 if (!scop->context)
5626 goto error;
5629 return scop;
5630 error:
5631 pet_scop_free(scop);
5632 return NULL;
5635 /* Construct a pet_scop from the given function.
5637 * If the scop was delimited by scop and endscop pragmas, then we override
5638 * the file offsets by those derived from the pragmas.
5640 struct pet_scop *PetScan::scan(FunctionDecl *fd)
5642 pet_scop *scop;
5643 Stmt *stmt;
5645 stmt = fd->getBody();
5647 if (options->autodetect)
5648 scop = extract(stmt, true);
5649 else {
5650 scop = scan(stmt);
5651 scop = pet_scop_update_start_end(scop, loc.start, loc.end);
5653 scop = pet_scop_detect_parameter_accesses(scop);
5654 scop = scan_arrays(scop);
5655 scop = add_parameter_bounds(scop);
5656 scop = pet_scop_gist(scop, value_bounds);
5658 return scop;