pet.cc

   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.
  11  *
  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.
  16  *
  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.
  28  *
  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  */
  34
  35 #include "config.h"
  36
  37 #include <stdlib.h>
  38 #include <map>
  39 #include <vector>
  40 #include <iostream>
  41 #include <llvm/ADT/OwningPtr.h>
  42 #include <llvm/Support/raw_ostream.h>
  43 #include <llvm/Support/ManagedStatic.h>
  44 #include <llvm/Support/Host.h>
  45 #include <clang/Basic/Version.h>
  46 #include <clang/Basic/FileSystemOptions.h>
  47 #include <clang/Basic/FileManager.h>
  48 #include <clang/Basic/TargetOptions.h>
  49 #include <clang/Basic/TargetInfo.h>
  50 #include <clang/Driver/Compilation.h>
  51 #include <clang/Driver/Driver.h>
  52 #include <clang/Driver/Tool.h>
  53 #include <clang/Frontend/CompilerInstance.h>
  54 #include <clang/Frontend/CompilerInvocation.h>
  55 #ifdef HAVE_BASIC_DIAGNOSTICOPTIONS_H
  56 #include <clang/Basic/DiagnosticOptions.h>
  57 #else
  58 #include <clang/Frontend/DiagnosticOptions.h>
  59 #endif
  60 #include <clang/Frontend/TextDiagnosticPrinter.h>
  61 #ifdef HAVE_LEX_HEADERSEARCHOPTIONS_H
  62 #include <clang/Lex/HeaderSearchOptions.h>
  63 #else
  64 #include <clang/Frontend/HeaderSearchOptions.h>
  65 #endif
  66 #include <clang/Frontend/LangStandard.h>
  67 #ifdef HAVE_LEX_PREPROCESSOROPTIONS_H
  68 #include <clang/Lex/PreprocessorOptions.h>
  69 #else
  70 #include <clang/Frontend/PreprocessorOptions.h>
  71 #endif
  72 #include <clang/Frontend/FrontendOptions.h>
  73 #include <clang/Frontend/Utils.h>
  74 #include <clang/Lex/HeaderSearch.h>
  75 #include <clang/Lex/Preprocessor.h>
  76 #include <clang/Lex/Pragma.h>
  77 #include <clang/AST/ASTContext.h>
  78 #include <clang/AST/ASTConsumer.h>
  79 #include <clang/Sema/Sema.h>
  80 #include <clang/Sema/SemaDiagnostic.h>
  81 #include <clang/Parse/Parser.h>
  82 #include <clang/Parse/ParseAST.h>
  83
  84 #include <isl/ctx.h>
  85 #include <isl/constraint.h>
  86
  87 #include <pet.h>
  88
  89 #include "options.h"
  90 #include "scan.h"
  91 #include "print.h"
  92
  93 #define ARRAY_SIZE(array) (sizeof(array)/sizeof(*array))
  94
  95 using namespace std;
  96 using namespace clang;
  97 using namespace clang::driver;
  98
  99 /* Called if we found something we didn't expect in one of the pragmas.
 100  * We'll provide more informative warnings later.
 101  */
 102 static void unsupported(Preprocessor &PP, SourceLocation loc)
 103 {
 104         DiagnosticsEngine &diag = PP.getDiagnostics();
 105         unsigned id = diag.getCustomDiagID(DiagnosticsEngine::Warning,
 106                                            "unsupported");
 107         DiagnosticBuilder B = diag.Report(loc, id);
 108 }
 109
 110 static int get_int(const char *s)
 111 {
 112         return s[0] == '"' ? atoi(s + 1) : atoi(s);
 113 }
 114
 115 static ValueDecl *get_value_decl(Sema &sema, Token &token)
 116 {
 117         IdentifierInfo *name;
 118         Decl *decl;
 119
 120         if (token.isNot(tok::identifier))
 121                 return NULL;
 122
 123         name = token.getIdentifierInfo();
 124         decl = sema.LookupSingleName(sema.TUScope, name,
 125                                 token.getLocation(), Sema::LookupOrdinaryName);
 126         return decl ? cast_or_null<ValueDecl>(decl) : NULL;
 127 }
 128
 129 /* Handle pragmas of the form
 130  *
 131  *      #pragma value_bounds identifier lower_bound upper_bound
 132  *
 133  * For each such pragma, add a mapping
 134  *      { identifier[] -> [i] : lower_bound <= i <= upper_bound }
 135  * to value_bounds.
 136  */
 137 struct PragmaValueBoundsHandler : public PragmaHandler {
 138         Sema &sema;
 139         isl_ctx *ctx;
 140         isl_union_map *value_bounds;
 141
 142         PragmaValueBoundsHandler(isl_ctx *ctx, Sema &sema) :
 143             PragmaHandler("value_bounds"), ctx(ctx), sema(sema) {
 144                 isl_space *space = isl_space_params_alloc(ctx, 0);
 145                 value_bounds = isl_union_map_empty(space);
 146         }
 147
 148         ~PragmaValueBoundsHandler() {
 149                 isl_union_map_free(value_bounds);
 150         }
 151
 152         virtual void HandlePragma(Preprocessor &PP,
 153                                   PragmaIntroducerKind Introducer,
 154                                   Token &ScopTok) {
 155                 isl_id *id;
 156                 isl_space *dim;
 157                 isl_map *map;
 158                 ValueDecl *vd;
 159                 Token token;
 160                 int lb;
 161                 int ub;
 162
 163                 PP.Lex(token);
 164                 vd = get_value_decl(sema, token);
 165                 if (!vd) {
 166                         unsupported(PP, token.getLocation());
 167                         return;
 168                 }
 169
 170                 PP.Lex(token);
 171                 if (!token.isLiteral()) {
 172                         unsupported(PP, token.getLocation());
 173                         return;
 174                 }
 175
 176                 lb = get_int(token.getLiteralData());
 177
 178                 PP.Lex(token);
 179                 if (!token.isLiteral()) {
 180                         unsupported(PP, token.getLocation());
 181                         return;
 182                 }
 183
 184                 ub = get_int(token.getLiteralData());
 185
 186                 dim = isl_space_alloc(ctx, 0, 0, 1);
 187                 map = isl_map_universe(dim);
 188                 map = isl_map_lower_bound_si(map, isl_dim_out, 0, lb);
 189                 map = isl_map_upper_bound_si(map, isl_dim_out, 0, ub);
 190                 id = isl_id_alloc(ctx, vd->getName().str().c_str(), vd);
 191                 map = isl_map_set_tuple_id(map, isl_dim_in, id);
 192
 193                 value_bounds = isl_union_map_add_map(value_bounds, map);
 194         }
 195 };
 196
 197 /* Given a variable declaration, check if it has an integer initializer
 198  * and if so, add a parameter corresponding to the variable to "value"
 199  * with its value fixed to the integer initializer and return the result.
 200  */
 201 static __isl_give isl_set *extract_initialization(__isl_take isl_set *value,
 202         ValueDecl *decl)
 203 {
 204         VarDecl *vd;
 205         Expr *expr;
 206         IntegerLiteral *il;
 207         isl_val *v;
 208         isl_ctx *ctx;
 209         isl_id *id;
 210         isl_space *space;
 211         isl_set *set;
 212
 213         vd = cast<VarDecl>(decl);
 214         if (!vd)
 215                 return value;
 216         if (!vd->getType()->isIntegerType())
 217                 return value;
 218         expr = vd->getInit();
 219         if (!expr)
 220                 return value;
 221         il = cast<IntegerLiteral>(expr);
 222         if (!il)
 223                 return value;
 224
 225         ctx = isl_set_get_ctx(value);
 226         id = isl_id_alloc(ctx, vd->getName().str().c_str(), vd);
 227         space = isl_space_params_alloc(ctx, 1);
 228         space = isl_space_set_dim_id(space, isl_dim_param, 0, id);
 229         set = isl_set_universe(space);
 230
 231         v = PetScan::extract_int(ctx, il);
 232         set = isl_set_fix_val(set, isl_dim_param, 0, v);
 233
 234         return isl_set_intersect(value, set);
 235 }
 236
 237 /* Handle pragmas of the form
 238  *
 239  *      #pragma parameter identifier lower_bound
 240  * and
 241  *      #pragma parameter identifier lower_bound upper_bound
 242  *
 243  * For each such pragma, intersect the context with the set
 244  * [identifier] -> { [] : lower_bound <= identifier <= upper_bound }
 245  */
 246 struct PragmaParameterHandler : public PragmaHandler {
 247         Sema &sema;
 248         isl_set *&context;
 249         isl_set *&context_value;
 250
 251         PragmaParameterHandler(Sema &sema, isl_set *&context,
 252                 isl_set *&context_value) :
 253                 PragmaHandler("parameter"), sema(sema), context(context),
 254                 context_value(context_value) {}
 255
 256         virtual void HandlePragma(Preprocessor &PP,
 257                                   PragmaIntroducerKind Introducer,
 258                                   Token &ScopTok) {
 259                 isl_id *id;
 260                 isl_ctx *ctx = isl_set_get_ctx(context);
 261                 isl_space *dim;
 262                 isl_set *set;
 263                 ValueDecl *vd;
 264                 Token token;
 265                 int lb;
 266                 int ub;
 267                 bool has_ub = false;
 268
 269                 PP.Lex(token);
 270                 vd = get_value_decl(sema, token);
 271                 if (!vd) {
 272                         unsupported(PP, token.getLocation());
 273                         return;
 274                 }
 275
 276                 PP.Lex(token);
 277                 if (!token.isLiteral()) {
 278                         unsupported(PP, token.getLocation());
 279                         return;
 280                 }
 281
 282                 lb = get_int(token.getLiteralData());
 283
 284                 PP.Lex(token);
 285                 if (token.isLiteral()) {
 286                         has_ub = true;
 287                         ub = get_int(token.getLiteralData());
 288                 } else if (token.isNot(tok::eod)) {
 289                         unsupported(PP, token.getLocation());
 290                         return;
 291                 }
 292
 293                 id = isl_id_alloc(ctx, vd->getName().str().c_str(), vd);
 294                 dim = isl_space_params_alloc(ctx, 1);
 295                 dim = isl_space_set_dim_id(dim, isl_dim_param, 0, id);
 296
 297                 set = isl_set_universe(dim);
 298
 299                 set = isl_set_lower_bound_si(set, isl_dim_param, 0, lb);
 300                 if (has_ub)
 301                         set = isl_set_upper_bound_si(set, isl_dim_param, 0, ub);
 302
 303                 context = isl_set_intersect(context, set);
 304
 305                 context_value = extract_initialization(context_value, vd);
 306         }
 307 };
 308
 309 /* Handle pragmas of the form
 310  *
 311  *      #pragma pencil independent
 312  *
 313  * For each such pragma, add an entry to the "independent" vector.
 314  */
 315 struct PragmaPencilHandler : public PragmaHandler {
 316         std::vector<Independent> &independent;
 317
 318         PragmaPencilHandler(std::vector<Independent> &independent) :
 319                 PragmaHandler("pencil"), independent(independent) {}
 320
 321         virtual void HandlePragma(Preprocessor &PP,
 322                                   PragmaIntroducerKind Introducer,
 323                                   Token &PencilTok) {
 324                 Token token;
 325                 IdentifierInfo *info;
 326
 327                 PP.Lex(token);
 328                 if (token.isNot(tok::identifier))
 329                         return;
 330
 331                 info = token.getIdentifierInfo();
 332                 if (!info->isStr("independent"))
 333                         return;
 334
 335                 PP.Lex(token);
 336                 if (token.isNot(tok::eod))
 337                         return;
 338
 339                 SourceManager &SM = PP.getSourceManager();
 340                 SourceLocation sloc = PencilTok.getLocation();
 341                 unsigned line = SM.getExpansionLineNumber(sloc);
 342                 independent.push_back(Independent(line));
 343         }
 344 };
 345
 346 #ifdef HAVE_TRANSLATELINECOL
 347
 348 /* Return a SourceLocation for line "line", column "col" of file "FID".
 349  */
 350 SourceLocation translateLineCol(SourceManager &SM, FileID FID, unsigned line,
 351         unsigned col)
 352 {
 353         return SM.translateLineCol(FID, line, col);
 354 }
 355
 356 #else
 357
 358 /* Return a SourceLocation for line "line", column "col" of file "FID".
 359  */
 360 SourceLocation translateLineCol(SourceManager &SM, FileID FID, unsigned line,
 361         unsigned col)
 362 {
 363         return SM.getLocation(SM.getFileEntryForID(FID), line, col);
 364 }
 365
 366 #endif
 367
 368 /* List of pairs of #pragma scop and #pragma endscop locations.
 369  */
 370 struct ScopLocList {
 371         std::vector<ScopLoc> list;
 372
 373         /* Add a new start (#pragma scop) location to the list.
 374          * If the last #pragma scop did not have a matching
 375          * #pragma endscop then overwrite it.
 376          */
 377         void add_start(unsigned line, unsigned start) {
 378                 ScopLoc loc;
 379
 380                 loc.start_line = line;
 381                 loc.start = start;
 382                 if (list.size() == 0 || list[list.size() - 1].end != 0)
 383                         list.push_back(loc);
 384                 else
 385                         list[list.size() - 1] = loc;
 386         }
 387
 388         /* Set the end location (#pragma endscop) of the last pair
 389          * in the list.
 390          * If there is no such pair of if the end of that pair
 391          * is already set, then ignore the spurious #pragma endscop.
 392          */
 393         void add_end(unsigned end) {
 394                 if (list.size() == 0 || list[list.size() - 1].end != 0)
 395                         return;
 396                 list[list.size() - 1].end = end;
 397         }
 398 };
 399
 400 /* Handle pragmas of the form
 401  *
 402  *      #pragma scop
 403  *
 404  * In particular, store the location of the line containing
 405  * the pragma in the list "scops".
 406  */
 407 struct PragmaScopHandler : public PragmaHandler {
 408         ScopLocList &scops;
 409
 410         PragmaScopHandler(ScopLocList &scops) :
 411                 PragmaHandler("scop"), scops(scops) {}
 412
 413         virtual void HandlePragma(Preprocessor &PP,
 414                                   PragmaIntroducerKind Introducer,
 415                                   Token &ScopTok) {
 416                 SourceManager &SM = PP.getSourceManager();
 417                 SourceLocation sloc = ScopTok.getLocation();
 418                 int line = SM.getExpansionLineNumber(sloc);
 419                 sloc = translateLineCol(SM, SM.getFileID(sloc), line, 1);
 420                 scops.add_start(line, SM.getFileOffset(sloc));
 421         }
 422 };
 423
 424 /* Handle pragmas of the form
 425  *
 426  *      #pragma endscop
 427  *
 428  * In particular, store the location of the line following the one containing
 429  * the pragma in the list "scops".
 430  */
 431 struct PragmaEndScopHandler : public PragmaHandler {
 432         ScopLocList &scops;
 433
 434         PragmaEndScopHandler(ScopLocList &scops) :
 435                 PragmaHandler("endscop"), scops(scops) {}
 436
 437         virtual void HandlePragma(Preprocessor &PP,
 438                                   PragmaIntroducerKind Introducer,
 439                                   Token &EndScopTok) {
 440                 SourceManager &SM = PP.getSourceManager();
 441                 SourceLocation sloc = EndScopTok.getLocation();
 442                 int line = SM.getExpansionLineNumber(sloc);
 443                 sloc = translateLineCol(SM, SM.getFileID(sloc), line + 1, 1);
 444                 scops.add_end(SM.getFileOffset(sloc));
 445         }
 446 };
 447
 448 /* Handle pragmas of the form
 449  *
 450  *      #pragma live-out identifier, identifier, ...
 451  *
 452  * Each identifier on the line is stored in live_out.
 453  */
 454 struct PragmaLiveOutHandler : public PragmaHandler {
 455         Sema &sema;
 456         set<ValueDecl *> &live_out;
 457
 458         PragmaLiveOutHandler(Sema &sema, set<ValueDecl *> &live_out) :
 459                 PragmaHandler("live"), sema(sema), live_out(live_out) {}
 460
 461         virtual void HandlePragma(Preprocessor &PP,
 462                                   PragmaIntroducerKind Introducer,
 463                                   Token &ScopTok) {
 464                 Token token;
 465
 466                 PP.Lex(token);
 467                 if (token.isNot(tok::minus))
 468                         return;
 469                 PP.Lex(token);
 470                 if (token.isNot(tok::identifier) ||
 471                     !token.getIdentifierInfo()->isStr("out"))
 472                         return;
 473
 474                 PP.Lex(token);
 475                 while (token.isNot(tok::eod)) {
 476                         ValueDecl *vd;
 477
 478                         vd = get_value_decl(sema, token);
 479                         if (!vd) {
 480                                 unsupported(PP, token.getLocation());
 481                                 return;
 482                         }
 483                         live_out.insert(vd);
 484                         PP.Lex(token);
 485                         if (token.is(tok::comma))
 486                                 PP.Lex(token);
 487                 }
 488         }
 489 };
 490
 491 /* For each array in "scop", set its value_bounds property
 492  * based on the infofrmation in "value_bounds" and
 493  * mark it as live_out if it appears in "live_out".
 494  */
 495 static void update_arrays(struct pet_scop *scop,
 496         __isl_take isl_union_map *value_bounds, set<ValueDecl *> &live_out)
 497 {
 498         set<ValueDecl *>::iterator lo_it;
 499         isl_ctx *ctx = isl_union_map_get_ctx(value_bounds);
 500
 501         if (!scop) {
 502                 isl_union_map_free(value_bounds);
 503                 return;
 504         }
 505
 506         for (int i = 0; i < scop->n_array; ++i) {
 507                 isl_id *id;
 508                 isl_space *space;
 509                 isl_map *bounds;
 510                 ValueDecl *decl;
 511                 pet_array *array = scop->arrays[i];
 512
 513                 id = isl_set_get_tuple_id(array->extent);
 514                 decl = (ValueDecl *)isl_id_get_user(id);
 515
 516                 space = isl_space_alloc(ctx, 0, 0, 1);
 517                 space = isl_space_set_tuple_id(space, isl_dim_in, id);
 518
 519                 bounds = isl_union_map_extract_map(value_bounds, space);
 520                 if (!isl_map_plain_is_empty(bounds))
 521                         array->value_bounds = isl_map_range(bounds);
 522                 else
 523                         isl_map_free(bounds);
 524
 525                 lo_it = live_out.find(decl);
 526                 if (lo_it != live_out.end())
 527                         array->live_out = 1;
 528         }
 529
 530         isl_union_map_free(value_bounds);
 531 }
 532
 533 /* Extract a pet_scop (if any) from each appropriate function.
 534  * Each detected scop is passed to "fn".
 535  * When autodetecting, at most one scop is extracted from each function.
 536  * If "function" is not NULL, then we only extract a pet_scop if the
 537  * name of the function matches.
 538  * If "autodetect" is false, then we only extract if we have seen
 539  * scop and endscop pragmas and if these are situated inside the function
 540  * body.
 541  */
 542 struct PetASTConsumer : public ASTConsumer {
 543         Preprocessor &PP;
 544         ASTContext &ast_context;
 545         DiagnosticsEngine &diags;
 546         ScopLocList &scops;
 547         std::vector<Independent> independent;
 548         const char *function;
 549         pet_options *options;
 550         isl_ctx *ctx;
 551         isl_set *context;
 552         isl_set *context_value;
 553         set<ValueDecl *> live_out;
 554         PragmaValueBoundsHandler *vb_handler;
 555         int (*fn)(struct pet_scop *scop, void *user);
 556         void *user;
 557         bool error;
 558
 559         PetASTConsumer(isl_ctx *ctx, Preprocessor &PP, ASTContext &ast_context,
 560                 DiagnosticsEngine &diags, ScopLocList &scops,
 561                 const char *function, pet_options *options,
 562                 int (*fn)(struct pet_scop *scop, void *user), void *user) :
 563                 ctx(ctx), PP(PP), ast_context(ast_context), diags(diags),
 564                 scops(scops), function(function), options(options),
 565                 vb_handler(NULL), fn(fn), user(user), error(false)
 566         {
 567                 isl_space *space;
 568                 space = isl_space_params_alloc(ctx, 0);
 569                 context = isl_set_universe(isl_space_copy(space));
 570                 context_value = isl_set_universe(space);
 571         }
 572
 573         ~PetASTConsumer() {
 574                 isl_set_free(context);
 575                 isl_set_free(context_value);
 576         }
 577
 578         void handle_value_bounds(Sema *sema) {
 579                 vb_handler = new PragmaValueBoundsHandler(ctx, *sema);
 580                 PP.AddPragmaHandler(vb_handler);
 581         }
 582
 583         /* Add all pragma handlers to this->PP.
 584          */
 585         void add_pragma_handlers(Sema *sema) {
 586                 PP.AddPragmaHandler(new PragmaParameterHandler(*sema, context,
 587                                                                 context_value));
 588                 PP.AddPragmaHandler(new PragmaPencilHandler(independent));
 589                 handle_value_bounds(sema);
 590         }
 591
 592         __isl_give isl_union_map *get_value_bounds() {
 593                 return isl_union_map_copy(vb_handler->value_bounds);
 594         }
 595
 596         /* Pass "scop" to "fn" after performing some postprocessing.
 597          * In particular, add the context and value_bounds constraints
 598          * speficied through pragmas, add reference identifiers and
 599          * reset user pointers on parameters and tuple ids.
 600          */
 601         void call_fn(pet_scop *scop) {
 602                 if (!scop)
 603                         return;
 604                 if (diags.hasErrorOccurred()) {
 605                         pet_scop_free(scop);
 606                         return;
 607                 }
 608                 scop->context = isl_set_intersect(scop->context,
 609                                                 isl_set_copy(context));
 610                 scop->context_value = isl_set_intersect(scop->context_value,
 611                                                 isl_set_copy(context_value));
 612
 613                 update_arrays(scop, get_value_bounds(), live_out);
 614
 615                 scop = pet_scop_add_ref_ids(scop);
 616                 scop = pet_scop_anonymize(scop);
 617
 618                 if (fn(scop, user) < 0)
 619                         error = true;
 620         }
 621
 622         /* For each explicitly marked scop (using pragmas),
 623          * extract the scop and call "fn" on it if it is inside "fd".
 624          */
 625         void scan_scops(FunctionDecl *fd) {
 626                 unsigned start, end;
 627                 vector<ScopLoc>::iterator it;
 628                 isl_union_map *vb = vb_handler->value_bounds;
 629                 SourceManager &SM = PP.getSourceManager();
 630                 pet_scop *scop;
 631
 632                 if (scops.list.size() == 0)
 633                         return;
 634
 635                 start = SM.getFileOffset(fd->getLocStart());
 636                 end = SM.getFileOffset(fd->getLocEnd());
 637
 638                 for (it = scops.list.begin(); it != scops.list.end(); ++it) {
 639                         ScopLoc loc = *it;
 640                         if (!loc.end)
 641                                 continue;
 642                         if (start > loc.end)
 643                                 continue;
 644                         if (end < loc.start)
 645                                 continue;
 646                         PetScan ps(PP, ast_context, loc, options,
 647                                     isl_union_map_copy(vb), independent);
 648                         scop = ps.scan(fd);
 649                         call_fn(scop);
 650                 }
 651         }
 652
 653         virtual HandleTopLevelDeclReturn HandleTopLevelDecl(DeclGroupRef dg) {
 654                 DeclGroupRef::iterator it;
 655
 656                 if (error)
 657                         return HandleTopLevelDeclContinue;
 658
 659                 for (it = dg.begin(); it != dg.end(); ++it) {
 660                         isl_union_map *vb = vb_handler->value_bounds;
 661                         FunctionDecl *fd = dyn_cast<clang::FunctionDecl>(*it);
 662                         if (!fd)
 663                                 continue;
 664                         if (!fd->hasBody())
 665                                 continue;
 666                         if (function &&
 667                             fd->getNameInfo().getAsString() != function)
 668                                 continue;
 669                         if (options->autodetect) {
 670                                 ScopLoc loc;
 671                                 pet_scop *scop;
 672                                 PetScan ps(PP, ast_context, loc, options,
 673                                             isl_union_map_copy(vb),
 674                                             independent);
 675                                 scop = ps.scan(fd);
 676                                 call_fn(scop);
 677                                 continue;
 678                         }
 679                         scan_scops(fd);
 680                 }
 681
 682                 return HandleTopLevelDeclContinue;
 683         }
 684 };
 685
 686 static const char *ResourceDir =
 687         CLANG_PREFIX "/lib/clang/" CLANG_VERSION_STRING;
 688
 689 static const char *implicit_functions[] = {
 690         "min", "max", "intMod", "intCeil", "intFloor", "ceild", "floord"
 691 };
 692
 693 static bool is_implicit(const IdentifierInfo *ident)
 694 {
 695         const char *name = ident->getNameStart();
 696         for (int i = 0; i < ARRAY_SIZE(implicit_functions); ++i)
 697                 if (!strcmp(name, implicit_functions[i]))
 698                         return true;
 699         return false;
 700 }
 701
 702 /* Ignore implicit function declaration warnings on
 703  * "min", "max", "ceild" and "floord" as we detect and handle these
 704  * in PetScan.
 705  */
 706 struct MyDiagnosticPrinter : public TextDiagnosticPrinter {
 707         const DiagnosticOptions *DiagOpts;
 708 #ifdef HAVE_BASIC_DIAGNOSTICOPTIONS_H
 709         MyDiagnosticPrinter(DiagnosticOptions *DO) :
 710                 TextDiagnosticPrinter(llvm::errs(), DO) {}
 711         virtual DiagnosticConsumer *clone(DiagnosticsEngine &Diags) const {
 712                 return new MyDiagnosticPrinter(&Diags.getDiagnosticOptions());
 713         }
 714 #else
 715         MyDiagnosticPrinter(const DiagnosticOptions &DO) :
 716                 DiagOpts(&DO), TextDiagnosticPrinter(llvm::errs(), DO) {}
 717         virtual DiagnosticConsumer *clone(DiagnosticsEngine &Diags) const {
 718                 return new MyDiagnosticPrinter(*DiagOpts);
 719         }
 720 #endif
 721         virtual void HandleDiagnostic(DiagnosticsEngine::Level level,
 722                                         const DiagnosticInfo &info) {
 723                 if (info.getID() == diag::ext_implicit_function_decl &&
 724                     info.getNumArgs() == 1 &&
 725                     info.getArgKind(0) == DiagnosticsEngine::ak_identifierinfo &&
 726                     is_implicit(info.getArgIdentifier(0)))
 727                         /* ignore warning */;
 728                 else
 729                         TextDiagnosticPrinter::HandleDiagnostic(level, info);
 730         }
 731 };
 732
 733 #ifdef USE_ARRAYREF
 734
 735 #ifdef HAVE_CXXISPRODUCTION
 736 static Driver *construct_driver(const char *binary, DiagnosticsEngine &Diags)
 737 {
 738         return new Driver(binary, llvm::sys::getDefaultTargetTriple(),
 739                             "", false, false, Diags);
 740 }
 741 #elif defined(HAVE_ISPRODUCTION)
 742 static Driver *construct_driver(const char *binary, DiagnosticsEngine &Diags)
 743 {
 744         return new Driver(binary, llvm::sys::getDefaultTargetTriple(),
 745                             "", false, Diags);
 746 }
 747 #else
 748 static Driver *construct_driver(const char *binary, DiagnosticsEngine &Diags)
 749 {
 750         return new Driver(binary, llvm::sys::getDefaultTargetTriple(),
 751                             "", Diags);
 752 }
 753 #endif
 754
 755 /* Create a CompilerInvocation object that stores the command line
 756  * arguments constructed by the driver.
 757  * The arguments are mainly useful for setting up the system include
 758  * paths on newer clangs and on some platforms.
 759  */
 760 static CompilerInvocation *construct_invocation(const char *filename,
 761         DiagnosticsEngine &Diags)
 762 {
 763         const char *binary = CLANG_PREFIX"/bin/clang";
 764         const llvm::OwningPtr<Driver> driver(construct_driver(binary, Diags));
 765         std::vector<const char *> Argv;
 766         Argv.push_back(binary);
 767         Argv.push_back(filename);
 768         const llvm::OwningPtr<Compilation> compilation(
 769                 driver->BuildCompilation(llvm::ArrayRef<const char *>(Argv)));
 770         JobList &Jobs = compilation->getJobs();
 771         if (Jobs.size() < 1)
 772                 return NULL;
 773
 774         Command *cmd = cast<Command>(*Jobs.begin());
 775         if (strcmp(cmd->getCreator().getName(), "clang"))
 776                 return NULL;
 777
 778         const ArgStringList *args = &cmd->getArguments();
 779
 780         CompilerInvocation *invocation = new CompilerInvocation;
 781         CompilerInvocation::CreateFromArgs(*invocation, args->data() + 1,
 782                                                 args->data() + args->size(),
 783                                                 Diags);
 784         return invocation;
 785 }
 786
 787 #else
 788
 789 static CompilerInvocation *construct_invocation(const char *filename,
 790         DiagnosticsEngine &Diags)
 791 {
 792         return NULL;
 793 }
 794
 795 #endif
 796
 797 #ifdef HAVE_BASIC_DIAGNOSTICOPTIONS_H
 798
 799 static MyDiagnosticPrinter *construct_printer(CompilerInstance *Clang)
 800 {
 801         return new MyDiagnosticPrinter(new DiagnosticOptions());
 802 }
 803
 804 #else
 805
 806 static MyDiagnosticPrinter *construct_printer(CompilerInstance *Clang)
 807 {
 808         return new MyDiagnosticPrinter(Clang->getDiagnosticOpts());
 809 }
 810
 811 #endif
 812
 813 #ifdef CREATETARGETINFO_TAKES_POINTER
 814
 815 static TargetInfo *create_target_info(CompilerInstance *Clang,
 816         DiagnosticsEngine &Diags)
 817 {
 818         TargetOptions &TO = Clang->getTargetOpts();
 819         TO.Triple = llvm::sys::getDefaultTargetTriple();
 820         return TargetInfo::CreateTargetInfo(Diags, &TO);
 821 }
 822
 823 #else
 824
 825 static TargetInfo *create_target_info(CompilerInstance *Clang,
 826         DiagnosticsEngine &Diags)
 827 {
 828         TargetOptions &TO = Clang->getTargetOpts();
 829         TO.Triple = llvm::sys::getDefaultTargetTriple();
 830         return TargetInfo::CreateTargetInfo(Diags, TO);
 831 }
 832
 833 #endif
 834
 835 #ifdef CREATEDIAGNOSTICS_TAKES_ARG
 836
 837 static void create_diagnostics(CompilerInstance *Clang)
 838 {
 839         Clang->createDiagnostics(0, NULL);
 840 }
 841
 842 #else
 843
 844 static void create_diagnostics(CompilerInstance *Clang)
 845 {
 846         Clang->createDiagnostics();
 847 }
 848
 849 #endif
 850
 851 #ifdef CREATEPREPROCESSOR_TAKES_TUKIND
 852
 853 static void create_preprocessor(CompilerInstance *Clang)
 854 {
 855         Clang->createPreprocessor(TU_Complete);
 856 }
 857
 858 #else
 859
 860 static void create_preprocessor(CompilerInstance *Clang)
 861 {
 862         Clang->createPreprocessor();
 863 }
 864
 865 #endif
 866
 867 #ifdef ADDPATH_TAKES_4_ARGUMENTS
 868
 869 void add_path(HeaderSearchOptions &HSO, string Path)
 870 {
 871         HSO.AddPath(Path, frontend::Angled, false, false);
 872 }
 873
 874 #else
 875
 876 void add_path(HeaderSearchOptions &HSO, string Path)
 877 {
 878         HSO.AddPath(Path, frontend::Angled, true, false, false);
 879 }
 880
 881 #endif
 882
 883 /* Add pet specific predefines to the preprocessor.
 884  *
 885  * We mimic the way <command line> is handled inside clang.
 886  */
 887 void add_predefines(Preprocessor &PP)
 888 {
 889         string s;
 890
 891         s = PP.getPredefines();
 892         s += "# 1 \"<pet>\" 1\n"
 893              "void __pencil_assume(int assumption);\n"
 894              "#define pencil_access(f) annotate(\"pencil_access(\" #f \")\")\n"
 895              "# 1 \"<built-in>\" 2\n";
 896         PP.setPredefines(s);
 897 }
 898
 899 /* Extract a pet_scop from each function in the C source file called "filename".
 900  * Each detected scop is passed to "fn".
 901  * If "function" is not NULL, only extract a pet_scop from the function
 902  * with that name.
 903  * If "autodetect" is set, extract any pet_scop we can find.
 904  * Otherwise, extract the pet_scop from the region delimited
 905  * by "scop" and "endscop" pragmas.
 906  *
 907  * We first set up the clang parser and then try to extract the
 908  * pet_scop from the appropriate function(s) in PetASTConsumer.
 909  */
 910 static int foreach_scop_in_C_source(isl_ctx *ctx,
 911         const char *filename, const char *function, pet_options *options,
 912         int (*fn)(struct pet_scop *scop, void *user), void *user)
 913 {
 914         CompilerInstance *Clang = new CompilerInstance();
 915         create_diagnostics(Clang);
 916         DiagnosticsEngine &Diags = Clang->getDiagnostics();
 917         Diags.setSuppressSystemWarnings(true);
 918         CompilerInvocation *invocation = construct_invocation(filename, Diags);
 919         if (invocation)
 920                 Clang->setInvocation(invocation);
 921         Diags.setClient(construct_printer(Clang));
 922         Clang->createFileManager();
 923         Clang->createSourceManager(Clang->getFileManager());
 924         TargetInfo *target = create_target_info(Clang, Diags);
 925         Clang->setTarget(target);
 926         CompilerInvocation::setLangDefaults(Clang->getLangOpts(), IK_C,
 927                                             LangStandard::lang_unspecified);
 928         HeaderSearchOptions &HSO = Clang->getHeaderSearchOpts();
 929         HSO.ResourceDir = ResourceDir;
 930         for (int i = 0; i < options->n_path; ++i)
 931                 add_path(HSO, options->paths[i]);
 932         PreprocessorOptions &PO = Clang->getPreprocessorOpts();
 933         for (int i = 0; i < options->n_define; ++i)
 934                 PO.addMacroDef(options->defines[i]);
 935         create_preprocessor(Clang);
 936         Preprocessor &PP = Clang->getPreprocessor();
 937         add_predefines(PP);
 938
 939         ScopLocList scops;
 940
 941         const FileEntry *file = Clang->getFileManager().getFile(filename);
 942         if (!file)
 943                 isl_die(ctx, isl_error_unknown, "unable to open file",
 944                         do { delete Clang; return -1; } while (0));
 945         Clang->getSourceManager().createMainFileID(file);
 946
 947         Clang->createASTContext();
 948         PetASTConsumer consumer(ctx, PP, Clang->getASTContext(), Diags,
 949                                 scops, function, options, fn, user);
 950         Sema *sema = new Sema(PP, Clang->getASTContext(), consumer);
 951
 952         if (!options->autodetect) {
 953                 PP.AddPragmaHandler(new PragmaScopHandler(scops));
 954                 PP.AddPragmaHandler(new PragmaEndScopHandler(scops));
 955                 PP.AddPragmaHandler(new PragmaLiveOutHandler(*sema,
 956                                                         consumer.live_out));
 957         }
 958
 959         consumer.add_pragma_handlers(sema);
 960
 961         Diags.getClient()->BeginSourceFile(Clang->getLangOpts(), &PP);
 962         ParseAST(*sema);
 963         Diags.getClient()->EndSourceFile();
 964
 965         delete sema;
 966         delete Clang;
 967
 968         return consumer.error ? -1 : 0;
 969 }
 970
 971 /* Extract a pet_scop from each function in the C source file called "filename".
 972  * Each detected scop is passed to "fn".
 973  *
 974  * This wrapper around foreach_scop_in_C_source is mainly used to ensure
 975  * that all objects on the stack (of that function) are destroyed before we
 976  * call llvm_shutdown.
 977  */
 978 static int pet_foreach_scop_in_C_source(isl_ctx *ctx,
 979         const char *filename, const char *function,
 980         int (*fn)(struct pet_scop *scop, void *user), void *user)
 981 {
 982         int r;
 983         pet_options *options;
 984         bool allocated = false;
 985
 986         options = isl_ctx_peek_pet_options(ctx);
 987         if (!options) {
 988                 options = pet_options_new_with_defaults();
 989                 allocated = true;
 990         }
 991
 992         r = foreach_scop_in_C_source(ctx, filename, function, options,
 993                                         fn, user);
 994         llvm::llvm_shutdown();
 995
 996         if (allocated)
 997                 pet_options_free(options);
 998
 999         return r;
1000 }
1001
1002 /* Store "scop" into the address pointed to by "user".
1003  * Return -1 to indicate that we are not interested in any further scops.
1004  * This function should therefore not be called a second call
1005  * so in principle there is no need to check if we have already set *user.
1006  */
1007 static int set_first_scop(pet_scop *scop, void *user)
1008 {
1009         pet_scop **p = (pet_scop **) user;
1010
1011         if (!*p)
1012                 *p = scop;
1013         else
1014                 pet_scop_free(scop);
1015
1016         return -1;
1017 }
1018
1019 /* Extract a pet_scop from the C source file called "filename".
1020  * If "function" is not NULL, extract the pet_scop from the function
1021  * with that name.
1022  *
1023  * We start extracting scops from every function and then abort
1024  * as soon as we have extracted one scop.
1025  */
1026 struct pet_scop *pet_scop_extract_from_C_source(isl_ctx *ctx,
1027         const char *filename, const char *function)
1028 {
1029         pet_scop *scop = NULL;
1030
1031         pet_foreach_scop_in_C_source(ctx, filename, function,
1032                                         &set_first_scop, &scop);
1033
1034         return scop;
1035 }
1036
1037 /* Internal data structure for pet_transform_C_source
1038  *
1039  * transform is the function that should be called to print a scop
1040  * in is the input source file
1041  * out is the output source file
1042  * end is the offset of the end of the previous scop (zero if we have not
1043  *      found any scop yet)
1044  * p is a printer that prints to out.
1045  */
1046 struct pet_transform_data {
1047         __isl_give isl_printer *(*transform)(__isl_take isl_printer *p,
1048                 struct pet_scop *scop, void *user);
1049         void *user;
1050
1051         FILE *in;
1052         FILE *out;
1053         unsigned end;
1054         isl_printer *p;
1055 };
1056
1057 /* This function is called each time a scop is detected.
1058  *
1059  * We first copy the input text code from the end of the previous scop
1060  * until the start of "scop" and then print the scop itself through
1061  * a call to data->transform.  We set up the printer to print
1062  * the transformed code with the same (initial) indentation as
1063  * the original code.
1064  * Finally, we keep track of the end of "scop" so that we can
1065  * continue copying when we find the next scop.
1066  *
1067  * Before calling data->transform, we store a pointer to the original
1068  * input file in the extended scop in case the user wants to call
1069  * pet_scop_print_original from the callback.
1070  */
1071 static int pet_transform(struct pet_scop *scop, void *user)
1072 {
1073         struct pet_transform_data *data = (struct pet_transform_data *) user;
1074         unsigned start;
1075
1076         start = pet_loc_get_start(scop->loc);
1077         if (copy(data->in, data->out, data->end, start) < 0)
1078                 goto error;
1079         data->end = pet_loc_get_end(scop->loc);
1080         scop = pet_scop_set_input_file(scop, data->in);
1081         data->p = isl_printer_set_indent_prefix(data->p,
1082                                         pet_loc_get_indent(scop->loc));
1083         data->p = data->transform(data->p, scop, data->user);
1084         if (!data->p)
1085                 return -1;
1086         return 0;
1087 error:
1088         pet_scop_free(scop);
1089         return -1;
1090 }
1091
1092 /* Transform the C source file "input" by rewriting each scop
1093  * through a call to "transform".
1094  * When autodetecting scops, at most one scop per function is rewritten.
1095  * The transformed C code is written to "output".
1096  *
1097  * For each scop we find, we first copy the input text code
1098  * from the end of the previous scop (or the beginning of the file
1099  * in case of the first scop) until the start of the scop
1100  * and then print the scop itself through a call to "transform".
1101  * At the end we copy everything from the end of the final scop
1102  * until the end of the input file to "output".
1103  */
1104 int pet_transform_C_source(isl_ctx *ctx, const char *input, FILE *out,
1105         __isl_give isl_printer *(*transform)(__isl_take isl_printer *p,
1106                 struct pet_scop *scop, void *user), void *user)
1107 {
1108         struct pet_transform_data data;
1109         int r;
1110
1111         data.in = stdin;
1112         data.out = out;
1113         if (input && strcmp(input, "-")) {
1114                 data.in = fopen(input, "r");
1115                 if (!data.in)
1116                         isl_die(ctx, isl_error_unknown, "unable to open file",
1117                                 return -1);
1118         }
1119
1120         data.p = isl_printer_to_file(ctx, data.out);
1121         data.p = isl_printer_set_output_format(data.p, ISL_FORMAT_C);
1122
1123         data.transform = transform;
1124         data.user = user;
1125         data.end = 0;
1126         r = pet_foreach_scop_in_C_source(ctx, input, NULL,
1127                                         &pet_transform, &data);
1128
1129         isl_printer_free(data.p);
1130         if (!data.p)
1131                 r = -1;
1132         if (r == 0 && copy(data.in, data.out, data.end, -1) < 0)
1133                 r = -1;
1134
1135         if (data.in != stdin)
1136                 fclose(data.in);
1137
1138         return r;
1139 }