pet.cc

   1 /*
   2  * Copyright 2011 Leiden University. All rights reserved.
   3  *
   4  * Redistribution and use in source and binary forms, with or without
   5  * modification, are permitted provided that the following conditions
   6  * are met:
   7  *
   8  *    1. Redistributions of source code must retain the above copyright
   9  *       notice, this list of conditions and the following disclaimer.
  10  *
  11  *    2. Redistributions in binary form must reproduce the above
  12  *       copyright notice, this list of conditions and the following
  13  *       disclaimer in the documentation and/or other materials provided
  14  *       with the distribution.
  15  *
  16  * THIS SOFTWARE IS PROVIDED BY LEIDEN UNIVERSITY ''AS IS'' AND ANY
  17  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  18  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  19  * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL LEIDEN UNIVERSITY OR
  20  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
  21  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
  22  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA,
  23  * OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  24  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  25  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  26  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  27  *
  28  * The views and conclusions contained in the software and documentation
  29  * are those of the authors and should not be interpreted as
  30  * representing official policies, either expressed or implied, of
  31  * Leiden University.
  32  */
  33
  34 #include <stdlib.h>
  35 #include <map>
  36 #include <iostream>
  37 #include <llvm/Support/raw_ostream.h>
  38 #include <llvm/Support/ManagedStatic.h>
  39 #include <llvm/Support/Host.h>
  40 #include <clang/Basic/Version.h>
  41 #include <clang/Basic/FileSystemOptions.h>
  42 #include <clang/Basic/FileManager.h>
  43 #include <clang/Basic/TargetOptions.h>
  44 #include <clang/Basic/TargetInfo.h>
  45 #include <clang/Frontend/CompilerInstance.h>
  46 #include <clang/Frontend/CompilerInvocation.h>
  47 #include <clang/Frontend/DiagnosticOptions.h>
  48 #include <clang/Frontend/TextDiagnosticPrinter.h>
  49 #include <clang/Frontend/HeaderSearchOptions.h>
  50 #include <clang/Frontend/LangStandard.h>
  51 #include <clang/Frontend/PreprocessorOptions.h>
  52 #include <clang/Frontend/FrontendOptions.h>
  53 #include <clang/Frontend/Utils.h>
  54 #include <clang/Lex/HeaderSearch.h>
  55 #include <clang/Lex/Preprocessor.h>
  56 #include <clang/Lex/Pragma.h>
  57 #include <clang/AST/ASTContext.h>
  58 #include <clang/AST/ASTConsumer.h>
  59 #include <clang/Sema/Sema.h>
  60 #include <clang/Sema/SemaDiagnostic.h>
  61 #include <clang/Parse/Parser.h>
  62 #include <clang/Parse/ParseAST.h>
  63
  64 #include <isl/ctx.h>
  65 #include <isl/constraint.h>
  66
  67 #include "scan.h"
  68
  69 #include "config.h"
  70
  71 #define ARRAY_SIZE(array) (sizeof(array)/sizeof(*array))
  72
  73 using namespace std;
  74 using namespace clang;
  75
  76 /* Called if we found something we didn't expect in one of the pragmas.
  77  * We'll provide more informative warnings later.
  78  */
  79 static void unsupported(Preprocessor &PP, SourceLocation loc)
  80 {
  81         Diagnostic &diag = PP.getDiagnostics();
  82         unsigned id = diag.getCustomDiagID(Diagnostic::Warning, "unsupported");
  83         DiagnosticBuilder B = diag.Report(loc, id);
  84 }
  85
  86 /* Set the lower and upper bounds on the given dimension of "set"
  87  * to "lb" and "ub".
  88  */
  89 static __isl_give isl_set *set_bounds(__isl_take isl_set *set,
  90         enum isl_dim_type type, int pos, int lb, int ub)
  91 {
  92         isl_constraint *c;
  93         isl_local_space *ls;
  94
  95         ls = isl_local_space_from_space(isl_set_get_space(set));
  96
  97         c = isl_inequality_alloc(isl_local_space_copy(ls));
  98         c = isl_constraint_set_coefficient_si(c, type, pos, 1);
  99         c = isl_constraint_set_constant_si(c, -lb);
 100         set = isl_set_add_constraint(set, c);
 101
 102         c = isl_inequality_alloc(ls);
 103         c = isl_constraint_set_coefficient_si(c, type, pos, -1);
 104         c = isl_constraint_set_constant_si(c, ub);
 105         set = isl_set_add_constraint(set, c);
 106
 107         return set;
 108 }
 109
 110 static int get_int(const char *s)
 111 {
 112         return s[0] == '"' ? atoi(s + 1) : atoi(s);
 113 }
 114
 115 static ValueDecl *get_value_decl(Sema &sema, Token &token)
 116 {
 117         IdentifierInfo *name;
 118         Decl *decl;
 119
 120         if (token.isNot(tok::identifier))
 121                 return NULL;
 122
 123         name = token.getIdentifierInfo();
 124         decl = sema.LookupSingleName(sema.TUScope, name,
 125                                 token.getLocation(), Sema::LookupOrdinaryName);
 126         return decl ? cast_or_null<ValueDecl>(decl) : NULL;
 127 }
 128
 129 /* Handle pragmas of the form
 130  *
 131  *      #pragma value_bounds identifier lower_bound upper_bound
 132  *
 133  * For each such pragma, add a mapping from the ValueDecl corresponding
 134  * to "identifier" to a set { [i] : lower_bound <= i <= upper_bound }
 135  * to the map value_bounds.
 136  */
 137 struct PragmaValueBoundsHandler : public PragmaHandler {
 138         Sema &sema;
 139         isl_ctx *ctx;
 140         map<ValueDecl *, isl_set *> &value_bounds;
 141
 142         PragmaValueBoundsHandler(isl_ctx *ctx, Sema &sema,
 143                                 map<ValueDecl *, isl_set *> &value_bounds) :
 144                 PragmaHandler("value_bounds"), ctx(ctx), sema(sema),
 145                 value_bounds(value_bounds) {}
 146
 147         virtual void HandlePragma(Preprocessor &PP,
 148                                   PragmaIntroducerKind Introducer,
 149                                   Token &ScopTok) {
 150                 isl_space *dim;
 151                 isl_set *set;
 152                 ValueDecl *vd;
 153                 Token token;
 154                 int lb;
 155                 int ub;
 156
 157                 PP.Lex(token);
 158                 vd = get_value_decl(sema, token);
 159                 if (!vd) {
 160                         unsupported(PP, token.getLocation());
 161                         return;
 162                 }
 163
 164                 PP.Lex(token);
 165                 if (!token.isLiteral()) {
 166                         unsupported(PP, token.getLocation());
 167                         return;
 168                 }
 169
 170                 lb = get_int(token.getLiteralData());
 171
 172                 PP.Lex(token);
 173                 if (!token.isLiteral()) {
 174                         unsupported(PP, token.getLocation());
 175                         return;
 176                 }
 177
 178                 ub = get_int(token.getLiteralData());
 179
 180                 dim = isl_space_set_alloc(ctx, 0, 1);
 181                 set = isl_set_universe(dim);
 182                 set = set_bounds(set, isl_dim_set, 0, lb, ub);
 183
 184                 value_bounds[vd] = set;
 185         }
 186 };
 187
 188 /* Given a variable declaration, check if it has an integer initializer
 189  * and if so, add a parameter corresponding to the variable to "value"
 190  * with its value fixed to the integer initializer and return the result.
 191  */
 192 static __isl_give isl_set *extract_initialization(__isl_take isl_set *value,
 193         ValueDecl *decl)
 194 {
 195         VarDecl *vd;
 196         Expr *expr;
 197         IntegerLiteral *il;
 198         isl_int v;
 199         isl_ctx *ctx;
 200         isl_id *id;
 201         isl_space *space;
 202         isl_set *set;
 203
 204         vd = cast<VarDecl>(decl);
 205         if (!vd)
 206                 return value;
 207         if (!vd->getType()->isIntegerType())
 208                 return value;
 209         expr = vd->getInit();
 210         if (!expr)
 211                 return value;
 212         il = cast<IntegerLiteral>(expr);
 213         if (!il)
 214                 return value;
 215
 216         ctx = isl_set_get_ctx(value);
 217         id = isl_id_alloc(ctx, vd->getName().str().c_str(), vd);
 218         space = isl_space_params_alloc(ctx, 1);
 219         space = isl_space_set_dim_id(space, isl_dim_param, 0, id);
 220         set = isl_set_universe(space);
 221
 222         isl_int_init(v);
 223         PetScan::extract_int(il, &v);
 224         set = isl_set_fix(set, isl_dim_param, 0, v);
 225         isl_int_clear(v);
 226
 227         return isl_set_intersect(value, set);
 228 }
 229
 230 /* Handle pragmas of the form
 231  *
 232  *      #pragma parameter identifier lower_bound upper_bound
 233  *
 234  * For each such pragma, intersect the context with the set
 235  * [identifier] -> { [] : lower_bound <= identifier <= upper_bound }
 236  */
 237 struct PragmaParameterHandler : public PragmaHandler {
 238         Sema &sema;
 239         isl_set *&context;
 240         isl_set *&context_value;
 241
 242         PragmaParameterHandler(Sema &sema, isl_set *&context,
 243                 isl_set *&context_value) :
 244                 PragmaHandler("parameter"), sema(sema), context(context),
 245                 context_value(context_value) {}
 246
 247         virtual void HandlePragma(Preprocessor &PP,
 248                                   PragmaIntroducerKind Introducer,
 249                                   Token &ScopTok) {
 250                 isl_id *id;
 251                 isl_ctx *ctx = isl_set_get_ctx(context);
 252                 isl_space *dim;
 253                 isl_set *set;
 254                 ValueDecl *vd;
 255                 Token token;
 256                 int lb;
 257                 int ub;
 258
 259                 PP.Lex(token);
 260                 vd = get_value_decl(sema, token);
 261                 if (!vd) {
 262                         unsupported(PP, token.getLocation());
 263                         return;
 264                 }
 265
 266                 PP.Lex(token);
 267                 if (!token.isLiteral()) {
 268                         unsupported(PP, token.getLocation());
 269                         return;
 270                 }
 271
 272                 lb = get_int(token.getLiteralData());
 273
 274                 PP.Lex(token);
 275                 if (!token.isLiteral()) {
 276                         unsupported(PP, token.getLocation());
 277                         return;
 278                 }
 279
 280                 ub = get_int(token.getLiteralData());
 281
 282                 id = isl_id_alloc(ctx, vd->getName().str().c_str(), vd);
 283                 dim = isl_space_params_alloc(ctx, 1);
 284                 dim = isl_space_set_dim_id(dim, isl_dim_param, 0, id);
 285
 286                 set = isl_set_universe(dim);
 287
 288                 set = set_bounds(set, isl_dim_param, 0, lb, ub);
 289
 290                 context = isl_set_intersect(context, set);
 291
 292                 context_value = extract_initialization(context_value, vd);
 293         }
 294 };
 295
 296 /* Handle pragmas of the form
 297  *
 298  *      #pragma scop
 299  *
 300  * In particular, store the current location in loc.start.
 301  */
 302 struct PragmaScopHandler : public PragmaHandler {
 303         ScopLoc &loc;
 304
 305         PragmaScopHandler(ScopLoc &loc) : PragmaHandler("scop"), loc(loc) {}
 306
 307         virtual void HandlePragma(Preprocessor &PP,
 308                                   PragmaIntroducerKind Introducer,
 309                                   Token &ScopTok) {
 310                 SourceManager &SM = PP.getSourceManager();
 311                 loc.start = SM.getFileOffset(ScopTok.getLocation());
 312         }
 313 };
 314
 315 /* Handle pragmas of the form
 316  *
 317  *      #pragma endscop
 318  *
 319  * In particular, store the current location in loc.end.
 320  */
 321 struct PragmaEndScopHandler : public PragmaHandler {
 322         ScopLoc &loc;
 323
 324         PragmaEndScopHandler(ScopLoc &loc) :
 325                 PragmaHandler("endscop"), loc(loc) {}
 326
 327         virtual void HandlePragma(Preprocessor &PP,
 328                                   PragmaIntroducerKind Introducer,
 329                                   Token &EndScopTok) {
 330                 SourceManager &SM = PP.getSourceManager();
 331                 loc.end = SM.getFileOffset(EndScopTok.getLocation());
 332         }
 333 };
 334
 335 /* Handle pragmas of the form
 336  *
 337  *      #pragma live-out identifier, identifier, ...
 338  *
 339  * Each identifier on the line is stored in live_out.
 340  */
 341 struct PragmaLiveOutHandler : public PragmaHandler {
 342         Sema &sema;
 343         set<ValueDecl *> &live_out;
 344
 345         PragmaLiveOutHandler(Sema &sema, set<ValueDecl *> &live_out) :
 346                 PragmaHandler("live"), sema(sema), live_out(live_out) {}
 347
 348         virtual void HandlePragma(Preprocessor &PP,
 349                                   PragmaIntroducerKind Introducer,
 350                                   Token &ScopTok) {
 351                 Token token;
 352
 353                 PP.Lex(token);
 354                 if (token.isNot(tok::minus))
 355                         return;
 356                 PP.Lex(token);
 357                 if (token.isNot(tok::identifier) ||
 358                     !token.getIdentifierInfo()->isStr("out"))
 359                         return;
 360
 361                 PP.Lex(token);
 362                 while (token.isNot(tok::eod)) {
 363                         ValueDecl *vd;
 364
 365                         vd = get_value_decl(sema, token);
 366                         if (!vd) {
 367                                 unsupported(PP, token.getLocation());
 368                                 return;
 369                         }
 370                         live_out.insert(vd);
 371                         PP.Lex(token);
 372                         if (token.is(tok::comma))
 373                                 PP.Lex(token);
 374                 }
 375         }
 376 };
 377
 378 /* Extract a pet_scop from the appropriate function.
 379  * If "function" is not NULL, then we only extract a pet_scop if the
 380  * name of the function matches.
 381  * If "autodetect" is false, then we only extract if we have seen
 382  * scop and endscop pragmas and if these are situated inside the function
 383  * body.
 384  */
 385 struct PetASTConsumer : public ASTConsumer {
 386         Preprocessor &PP;
 387         ASTContext &ast_context;
 388         ScopLoc &loc;
 389         const char *function;
 390         bool autodetect;
 391         isl_ctx *ctx;
 392         struct pet_scop *scop;
 393
 394         PetASTConsumer(isl_ctx *ctx, Preprocessor &PP, ASTContext &ast_context,
 395                 ScopLoc &loc, const char *function, bool autodetect) :
 396                 ctx(ctx), PP(PP), ast_context(ast_context), loc(loc),
 397                 scop(NULL), function(function), autodetect(autodetect) { }
 398
 399         virtual void HandleTopLevelDecl(DeclGroupRef dg) {
 400                 DeclGroupRef::iterator it;
 401
 402                 if (scop)
 403                         return;
 404                 for (it = dg.begin(); it != dg.end(); ++it) {
 405                         FunctionDecl *fd = dyn_cast<clang::FunctionDecl>(*it);
 406                         if (!fd)
 407                                 continue;
 408                         if (!fd->hasBody())
 409                                 continue;
 410                         if (function &&
 411                             fd->getNameInfo().getAsString() != function)
 412                                 continue;
 413                         if (autodetect) {
 414                                 PetScan ps(ctx, PP, ast_context, loc, 1);
 415                                 scop = ps.scan(fd);
 416                                 if (scop)
 417                                         break;
 418                                 else
 419                                         continue;
 420                         }
 421                         if (!loc.end)
 422                                 continue;
 423                         SourceManager &SM = PP.getSourceManager();
 424                         if (SM.getFileOffset(fd->getLocStart()) > loc.end)
 425                                 continue;
 426                         if (SM.getFileOffset(fd->getLocEnd()) < loc.start)
 427                                 continue;
 428                         PetScan ps(ctx, PP, ast_context, loc, 0);
 429                         scop = ps.scan(fd);
 430                         break;
 431                 }
 432         }
 433 };
 434
 435 static const char *ResourceDir = CLANG_PREFIX"/lib/clang/"CLANG_VERSION_STRING;
 436
 437 static const char *implicit_functions[] = {
 438         "min", "max", "ceild", "floord"
 439 };
 440
 441 static bool is_implicit(const IdentifierInfo *ident)
 442 {
 443         const char *name = ident->getNameStart();
 444         for (int i = 0; i < ARRAY_SIZE(implicit_functions); ++i)
 445                 if (!strcmp(name, implicit_functions[i]))
 446                         return true;
 447         return false;
 448 }
 449
 450 /* Ignore implicit function declaration warnings on
 451  * "min", "max", "ceild" and "floord" as we detect and handle these
 452  * in PetScan.
 453  */
 454 struct MyDiagnosticPrinter : public TextDiagnosticPrinter {
 455         MyDiagnosticPrinter(const DiagnosticOptions &DO) :
 456                 TextDiagnosticPrinter(llvm::errs(), DO) {}
 457         virtual void HandleDiagnostic(Diagnostic::Level level,
 458                                         const DiagnosticInfo &info) {
 459                 if (info.getID() == diag::ext_implicit_function_decl &&
 460                     info.getNumArgs() == 1 &&
 461                     info.getArgKind(0) == Diagnostic::ak_identifierinfo &&
 462                     is_implicit(info.getArgIdentifier(0)))
 463                         /* ignore warning */;
 464                 else
 465                         TextDiagnosticPrinter::HandleDiagnostic(level, info);
 466         }
 467 };
 468
 469 static void update_arrays(struct pet_scop *scop,
 470         map<ValueDecl *, isl_set *> &value_bounds,
 471         set<ValueDecl *> &live_out)
 472 {
 473         map<ValueDecl *, isl_set *>::iterator vb_it;
 474         set<ValueDecl *>::iterator lo_it;
 475
 476         if (!scop)
 477                 return;
 478
 479         for (int i = 0; i < scop->n_array; ++i) {
 480                 isl_id *id;
 481                 ValueDecl *decl;
 482                 pet_array *array = scop->arrays[i];
 483
 484                 id = isl_set_get_tuple_id(array->extent);
 485                 decl = (ValueDecl *)isl_id_get_user(id);
 486                 isl_id_free(id);
 487
 488                 vb_it = value_bounds.find(decl);
 489                 if (vb_it != value_bounds.end())
 490                         array->value_bounds = isl_set_copy(vb_it->second);
 491
 492                 lo_it = live_out.find(decl);
 493                 if (lo_it != live_out.end())
 494                         array->live_out = 1;
 495         }
 496 }
 497
 498 /* Extract a pet_scop from the C source file called "filename".
 499  * If "function" is not NULL, extract the pet_scop from the function
 500  * with that name.
 501  * If "autodetect" is set, extract any pet_scop we can find.
 502  * Otherwise, extract the pet_scop from the region delimited
 503  * by "scop" and "endscop" pragmas.
 504  *
 505  * We first set up the clang parser and then try to extract the
 506  * pet_scop from the appropriate function in PetASTConsumer.
 507  * If we have found a pet_scop, we add the context and value_bounds
 508  * constraints specified through pragmas.
 509  */
 510 struct pet_scop *pet_scop_extract_from_C_source(isl_ctx *ctx,
 511         const char *filename, const char *function, int autodetect)
 512 {
 513         isl_space *dim;
 514         isl_set *context;
 515         isl_set *context_value;
 516         set<ValueDecl *> live_out;
 517         map<ValueDecl *, isl_set *> value_bounds;
 518         map<ValueDecl *, isl_set *>::iterator vb_it;
 519
 520         CompilerInstance *Clang = new CompilerInstance();
 521         DiagnosticOptions DO;
 522         Clang->createDiagnostics(0, NULL, new MyDiagnosticPrinter(DO));
 523         Diagnostic &Diags = Clang->getDiagnostics();
 524         Diags.setSuppressSystemWarnings(true);
 525         Clang->createFileManager();
 526         Clang->createSourceManager(Clang->getFileManager());
 527         TargetOptions TO;
 528         TO.Triple = llvm::sys::getHostTriple();
 529         TargetInfo *target = TargetInfo::CreateTargetInfo(Diags, TO);
 530         Clang->setTarget(target);
 531         CompilerInvocation::setLangDefaults(Clang->getLangOpts(), IK_C,
 532                                             LangStandard::lang_unspecified);
 533         Clang->getHeaderSearchOpts().ResourceDir = ResourceDir;
 534         Clang->createPreprocessor();
 535         Preprocessor &PP = Clang->getPreprocessor();
 536
 537         ScopLoc loc;
 538
 539         const FileEntry *file = Clang->getFileManager().getFile(filename);
 540         if (!file)
 541                 isl_die(ctx, isl_error_unknown, "unable to open file",
 542                         return NULL);
 543         Clang->getSourceManager().createMainFileID(file);
 544
 545         Clang->createASTContext();
 546         PetASTConsumer consumer(ctx, PP, Clang->getASTContext(),
 547                                 loc, function, autodetect);
 548         Sema *sema = new Sema(PP, Clang->getASTContext(), consumer);
 549
 550         if (!autodetect) {
 551                 PP.AddPragmaHandler(new PragmaScopHandler(loc));
 552                 PP.AddPragmaHandler(new PragmaEndScopHandler(loc));
 553                 PP.AddPragmaHandler(new PragmaLiveOutHandler(*sema, live_out));
 554         }
 555
 556         dim = isl_space_params_alloc(ctx, 0);
 557         context = isl_set_universe(isl_space_copy(dim));
 558         context_value = isl_set_universe(dim);
 559         PP.AddPragmaHandler(new PragmaParameterHandler(*sema, context,
 560                                                         context_value));
 561         PP.AddPragmaHandler(new PragmaValueBoundsHandler(ctx, *sema, value_bounds));
 562
 563         Diags.getClient()->BeginSourceFile(Clang->getLangOpts(), &PP);
 564         ParseAST(*sema);
 565         Diags.getClient()->EndSourceFile();
 566
 567         delete sema;
 568         delete Clang;
 569         llvm::llvm_shutdown();
 570
 571         if (consumer.scop) {
 572                 consumer.scop->context = isl_set_intersect(context,
 573                                                     consumer.scop->context);
 574                 consumer.scop->context_value = isl_set_intersect(context_value,
 575                                                 consumer.scop->context_value);
 576         } else {
 577                 isl_set_free(context);
 578                 isl_set_free(context_value);
 579         }
 580
 581         update_arrays(consumer.scop, value_bounds, live_out);
 582
 583         for (vb_it = value_bounds.begin(); vb_it != value_bounds.end(); vb_it++)
 584                 isl_set_free(vb_it->second);
 585
 586         return consumer.scop;
 587 }