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