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