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
  94         c = isl_inequality_alloc(isl_set_get_space(set));
  95         isl_constraint_set_coefficient_si(c, type, pos, 1);
  96         isl_constraint_set_constant_si(c, -lb);
  97         set = isl_set_add_constraint(set, c);
  98
  99         c = isl_inequality_alloc(isl_set_get_space(set));
 100         isl_constraint_set_coefficient_si(c, type, pos, -1);
 101         isl_constraint_set_constant_si(c, ub);
 102         set = isl_set_add_constraint(set, c);
 103
 104         return set;
 105 }
 106
 107 static int get_int(const char *s)
 108 {
 109         return s[0] == '"' ? atoi(s + 1) : atoi(s);
 110 }
 111
 112 static ValueDecl *get_value_decl(Sema &sema, Token &token)
 113 {
 114         IdentifierInfo *name;
 115         Decl *decl;
 116
 117         if (token.isNot(tok::identifier))
 118                 return NULL;
 119
 120         name = token.getIdentifierInfo();
 121         decl = sema.LookupSingleName(sema.TUScope, name,
 122                                 token.getLocation(), Sema::LookupOrdinaryName);
 123         return decl ? cast_or_null<ValueDecl>(decl) : NULL;
 124 }
 125
 126 /* Handle pragmas of the form
 127  *
 128  *      #pragma value_bounds identifier lower_bound upper_bound
 129  *
 130  * For each such pragma, add a mapping from the ValueDecl corresponding
 131  * to "identifier" to a set { [i] : lower_bound <= i <= upper_bound }
 132  * to the map value_bounds.
 133  */
 134 struct PragmaValueBoundsHandler : public PragmaHandler {
 135         Sema &sema;
 136         isl_ctx *ctx;
 137         map<ValueDecl *, isl_set *> &value_bounds;
 138
 139         PragmaValueBoundsHandler(isl_ctx *ctx, Sema &sema,
 140                                 map<ValueDecl *, isl_set *> &value_bounds) :
 141                 PragmaHandler("value_bounds"), ctx(ctx), sema(sema),
 142                 value_bounds(value_bounds) {}
 143
 144         virtual void HandlePragma(Preprocessor &PP,
 145                                   PragmaIntroducerKind Introducer,
 146                                   Token &ScopTok) {
 147                 isl_space *dim;
 148                 isl_set *set;
 149                 ValueDecl *vd;
 150                 Token token;
 151                 int lb;
 152                 int ub;
 153
 154                 PP.Lex(token);
 155                 vd = get_value_decl(sema, token);
 156                 if (!vd) {
 157                         unsupported(PP, token.getLocation());
 158                         return;
 159                 }
 160
 161                 PP.Lex(token);
 162                 if (!token.isLiteral()) {
 163                         unsupported(PP, token.getLocation());
 164                         return;
 165                 }
 166
 167                 lb = get_int(token.getLiteralData());
 168
 169                 PP.Lex(token);
 170                 if (!token.isLiteral()) {
 171                         unsupported(PP, token.getLocation());
 172                         return;
 173                 }
 174
 175                 ub = get_int(token.getLiteralData());
 176
 177                 dim = isl_space_set_alloc(ctx, 0, 1);
 178                 set = isl_set_universe(dim);
 179                 set = set_bounds(set, isl_dim_set, 0, lb, ub);
 180
 181                 value_bounds[vd] = set;
 182         }
 183 };
 184
 185 /* Handle pragmas of the form
 186  *
 187  *      #pragma parameter identifier lower_bound upper_bound
 188  *
 189  * For each such pragma, intersect the context with the set
 190  * [identifier] -> { [] : lower_bound <= identifier <= upper_bound }
 191  */
 192 struct PragmaParameterHandler : public PragmaHandler {
 193         Sema &sema;
 194         isl_set *&context;
 195
 196         PragmaParameterHandler(Sema &sema, isl_set *&context) :
 197                 PragmaHandler("parameter"), sema(sema), context(context) {}
 198
 199         virtual void HandlePragma(Preprocessor &PP,
 200                                   PragmaIntroducerKind Introducer,
 201                                   Token &ScopTok) {
 202                 isl_id *id;
 203                 isl_ctx *ctx = isl_set_get_ctx(context);
 204                 isl_space *dim;
 205                 isl_set *set;
 206                 ValueDecl *vd;
 207                 Token token;
 208                 int lb;
 209                 int ub;
 210
 211                 PP.Lex(token);
 212                 vd = get_value_decl(sema, token);
 213                 if (!vd) {
 214                         unsupported(PP, token.getLocation());
 215                         return;
 216                 }
 217
 218                 PP.Lex(token);
 219                 if (!token.isLiteral()) {
 220                         unsupported(PP, token.getLocation());
 221                         return;
 222                 }
 223
 224                 lb = get_int(token.getLiteralData());
 225
 226                 PP.Lex(token);
 227                 if (!token.isLiteral()) {
 228                         unsupported(PP, token.getLocation());
 229                         return;
 230                 }
 231
 232                 ub = get_int(token.getLiteralData());
 233
 234                 id = isl_id_alloc(ctx, vd->getName().str().c_str(), vd);
 235                 dim = isl_space_set_alloc(ctx, 1, 0);
 236                 dim = isl_space_set_dim_id(dim, isl_dim_param, 0, id);
 237
 238                 set = isl_set_universe(dim);
 239
 240                 set = set_bounds(set, isl_dim_param, 0, lb, ub);
 241
 242                 context = isl_set_intersect(context, set);
 243         }
 244 };
 245
 246 /* Handle pragmas of the form
 247  *
 248  *      #pragma scop
 249  *
 250  * In particular, store the current location in loc.start.
 251  */
 252 struct PragmaScopHandler : public PragmaHandler {
 253         ScopLoc &loc;
 254
 255         PragmaScopHandler(ScopLoc &loc) : PragmaHandler("scop"), loc(loc) {}
 256
 257         virtual void HandlePragma(Preprocessor &PP,
 258                                   PragmaIntroducerKind Introducer,
 259                                   Token &ScopTok) {
 260                 SourceManager &SM = PP.getSourceManager();
 261                 loc.start = SM.getFileOffset(ScopTok.getLocation());
 262         }
 263 };
 264
 265 /* Handle pragmas of the form
 266  *
 267  *      #pragma endscop
 268  *
 269  * In particular, store the current location in loc.end.
 270  */
 271 struct PragmaEndScopHandler : public PragmaHandler {
 272         ScopLoc &loc;
 273
 274         PragmaEndScopHandler(ScopLoc &loc) :
 275                 PragmaHandler("endscop"), loc(loc) {}
 276
 277         virtual void HandlePragma(Preprocessor &PP,
 278                                   PragmaIntroducerKind Introducer,
 279                                   Token &EndScopTok) {
 280                 SourceManager &SM = PP.getSourceManager();
 281                 loc.end = SM.getFileOffset(EndScopTok.getLocation());
 282         }
 283 };
 284
 285 /* Handle pragmas of the form
 286  *
 287  *      #pragma live-out identifier, identifier, ...
 288  *
 289  * Each identifier on the line is stored in live_out.
 290  */
 291 struct PragmaLiveOutHandler : public PragmaHandler {
 292         Sema &sema;
 293         set<ValueDecl *> &live_out;
 294
 295         PragmaLiveOutHandler(Sema &sema, set<ValueDecl *> &live_out) :
 296                 PragmaHandler("live"), sema(sema), live_out(live_out) {}
 297
 298         virtual void HandlePragma(Preprocessor &PP,
 299                                   PragmaIntroducerKind Introducer,
 300                                   Token &ScopTok) {
 301                 Token token;
 302
 303                 PP.Lex(token);
 304                 if (token.isNot(tok::minus))
 305                         return;
 306                 PP.Lex(token);
 307                 if (token.isNot(tok::identifier) ||
 308                     !token.getIdentifierInfo()->isStr("out"))
 309                         return;
 310
 311                 PP.Lex(token);
 312                 while (token.isNot(tok::eod)) {
 313                         ValueDecl *vd;
 314
 315                         vd = get_value_decl(sema, token);
 316                         if (!vd) {
 317                                 unsupported(PP, token.getLocation());
 318                                 return;
 319                         }
 320                         live_out.insert(vd);
 321                         PP.Lex(token);
 322                         if (token.is(tok::comma))
 323                                 PP.Lex(token);
 324                 }
 325         }
 326 };
 327
 328 /* Extract a pet_scop from the appropriate function.
 329  * If "function" is not NULL, then we only extract a pet_scop if the
 330  * name of the function matches.
 331  * If "autodetect" is false, then we only extract if we have seen
 332  * scop and endscop pragmas and if these are situated inside the function
 333  * body.
 334  */
 335 struct PetASTConsumer : public ASTConsumer {
 336         Preprocessor &PP;
 337         ASTContext &ast_context;
 338         ScopLoc &loc;
 339         const char *function;
 340         bool autodetect;
 341         isl_ctx *ctx;
 342         struct pet_scop *scop;
 343
 344         PetASTConsumer(isl_ctx *ctx, Preprocessor &PP, ASTContext &ast_context,
 345                 ScopLoc &loc, const char *function, bool autodetect) :
 346                 ctx(ctx), PP(PP), ast_context(ast_context), loc(loc),
 347                 scop(NULL), function(function), autodetect(autodetect) { }
 348
 349         virtual void HandleTopLevelDecl(DeclGroupRef dg) {
 350                 DeclGroupRef::iterator it;
 351
 352                 if (scop)
 353                         return;
 354                 for (it = dg.begin(); it != dg.end(); ++it) {
 355                         FunctionDecl *fd = dyn_cast<clang::FunctionDecl>(*it);
 356                         if (!fd)
 357                                 continue;
 358                         if (!fd->hasBody())
 359                                 continue;
 360                         if (function &&
 361                             fd->getNameInfo().getAsString() != function)
 362                                 continue;
 363                         if (autodetect) {
 364                                 PetScan ps(ctx, PP, ast_context, loc, 1);
 365                                 scop = ps.scan(fd);
 366                                 if (scop)
 367                                         break;
 368                                 else
 369                                         continue;
 370                         }
 371                         if (!loc.end)
 372                                 continue;
 373                         SourceManager &SM = PP.getSourceManager();
 374                         if (SM.getFileOffset(fd->getLocStart()) > loc.end)
 375                                 continue;
 376                         if (SM.getFileOffset(fd->getLocEnd()) < loc.start)
 377                                 continue;
 378                         PetScan ps(ctx, PP, ast_context, loc, 0);
 379                         scop = ps.scan(fd);
 380                         break;
 381                 }
 382         }
 383 };
 384
 385 static const char *ResourceDir = CLANG_PREFIX"/lib/clang/"CLANG_VERSION_STRING;
 386
 387 static const char *implicit_functions[] = {
 388         "min", "max", "ceild", "floord"
 389 };
 390
 391 static bool is_implicit(const IdentifierInfo *ident)
 392 {
 393         const char *name = ident->getNameStart();
 394         for (int i = 0; i < ARRAY_SIZE(implicit_functions); ++i)
 395                 if (!strcmp(name, implicit_functions[i]))
 396                         return true;
 397         return false;
 398 }
 399
 400 /* Ignore implicit function declaration warnings on
 401  * "min", "max", "ceild" and "floord" as we detect and handle these
 402  * in PetScan.
 403  */
 404 struct MyDiagnosticPrinter : public TextDiagnosticPrinter {
 405         MyDiagnosticPrinter(const DiagnosticOptions &DO) :
 406                 TextDiagnosticPrinter(llvm::errs(), DO) {}
 407         virtual void HandleDiagnostic(Diagnostic::Level level,
 408                                         const DiagnosticInfo &info) {
 409                 if (info.getID() == diag::ext_implicit_function_decl &&
 410                     info.getNumArgs() == 1 &&
 411                     info.getArgKind(0) == Diagnostic::ak_identifierinfo &&
 412                     is_implicit(info.getArgIdentifier(0)))
 413                         /* ignore warning */;
 414                 else
 415                         TextDiagnosticPrinter::HandleDiagnostic(level, info);
 416         }
 417 };
 418
 419 static void update_arrays(struct pet_scop *scop,
 420         map<ValueDecl *, isl_set *> &value_bounds,
 421         set<ValueDecl *> &live_out)
 422 {
 423         map<ValueDecl *, isl_set *>::iterator vb_it;
 424         set<ValueDecl *>::iterator lo_it;
 425
 426         if (!scop)
 427                 return;
 428
 429         for (int i = 0; i < scop->n_array; ++i) {
 430                 isl_id *id;
 431                 ValueDecl *decl;
 432                 pet_array *array = scop->arrays[i];
 433
 434                 id = isl_set_get_tuple_id(array->extent);
 435                 decl = (ValueDecl *)isl_id_get_user(id);
 436                 isl_id_free(id);
 437
 438                 vb_it = value_bounds.find(decl);
 439                 if (vb_it != value_bounds.end())
 440                         array->value_bounds = isl_set_copy(vb_it->second);
 441
 442                 lo_it = live_out.find(decl);
 443                 if (lo_it != live_out.end())
 444                         array->live_out = 1;
 445         }
 446 }
 447
 448 /* Extract a pet_scop from the C source file called "filename".
 449  * If "function" is not NULL, extract the pet_scop from the function
 450  * with that name.
 451  * If "autodetect" is set, extract any pet_scop we can find.
 452  * Otherwise, extract the pet_scop from the region delimited
 453  * by "scop" and "endscop" pragmas.
 454  *
 455  * We first set up the clang parser and then try to extract the
 456  * pet_scop from the appropriate function in PetASTConsumer.
 457  * If we have found a pet_scop, we add the context and value_bounds
 458  * constraints specified through pragmas.
 459  */
 460 struct pet_scop *pet_scop_extract_from_C_source(isl_ctx *ctx,
 461         const char *filename, const char *function, int autodetect)
 462 {
 463         isl_space *dim;
 464         isl_set *context;
 465         set<ValueDecl *> live_out;
 466         map<ValueDecl *, isl_set *> value_bounds;
 467         map<ValueDecl *, isl_set *>::iterator vb_it;
 468
 469         CompilerInstance *Clang = new CompilerInstance();
 470         DiagnosticOptions DO;
 471         Clang->createDiagnostics(0, NULL, new MyDiagnosticPrinter(DO));
 472         Diagnostic &Diags = Clang->getDiagnostics();
 473         Diags.setSuppressSystemWarnings(true);
 474         Clang->createFileManager();
 475         Clang->createSourceManager(Clang->getFileManager());
 476         TargetOptions TO;
 477         TO.Triple = llvm::sys::getHostTriple();
 478         TargetInfo *target = TargetInfo::CreateTargetInfo(Diags, TO);
 479         Clang->setTarget(target);
 480         CompilerInvocation::setLangDefaults(Clang->getLangOpts(), IK_C,
 481                                             LangStandard::lang_unspecified);
 482         Clang->getHeaderSearchOpts().ResourceDir = ResourceDir;
 483         Clang->createPreprocessor();
 484         Preprocessor &PP = Clang->getPreprocessor();
 485
 486         ScopLoc loc;
 487
 488         const FileEntry *file = Clang->getFileManager().getFile(filename);
 489         if (!file)
 490                 isl_die(ctx, isl_error_unknown, "unable to open file",
 491                         return NULL);
 492         Clang->getSourceManager().createMainFileID(file);
 493
 494         Clang->createASTContext();
 495         PetASTConsumer consumer(ctx, PP, Clang->getASTContext(),
 496                                 loc, function, autodetect);
 497         Sema *sema = new Sema(PP, Clang->getASTContext(), consumer);
 498
 499         if (!autodetect) {
 500                 PP.AddPragmaHandler(new PragmaScopHandler(loc));
 501                 PP.AddPragmaHandler(new PragmaEndScopHandler(loc));
 502                 PP.AddPragmaHandler(new PragmaLiveOutHandler(*sema, live_out));
 503         }
 504
 505         dim = isl_space_params_alloc(ctx, 0);
 506         context = isl_set_universe(dim);
 507         PP.AddPragmaHandler(new PragmaParameterHandler(*sema, context));
 508         PP.AddPragmaHandler(new PragmaValueBoundsHandler(ctx, *sema, value_bounds));
 509
 510         Diags.getClient()->BeginSourceFile(Clang->getLangOpts(), &PP);
 511         ParseAST(*sema);
 512         Diags.getClient()->EndSourceFile();
 513
 514         delete sema;
 515         delete Clang;
 516         llvm::llvm_shutdown();
 517
 518         if (consumer.scop)
 519                 consumer.scop->context = isl_set_intersect(context,
 520                                                     consumer.scop->context);
 521         else
 522                 isl_set_free(context);
 523
 524         update_arrays(consumer.scop, value_bounds, live_out);
 525
 526         for (vb_it = value_bounds.begin(); vb_it != value_bounds.end(); vb_it++)
 527                 isl_set_free(vb_it->second);
 528
 529         return consumer.scop;
 530 }