pet.cc

   1 #include <stdlib.h>
   2 #include <map>
   3 #include <iostream>
   4 #include <llvm/Support/raw_ostream.h>
   5 #include <llvm/Support/ManagedStatic.h>
   6 #include <llvm/Support/Host.h>
   7 #include <clang/Basic/Version.h>
   8 #include <clang/Basic/FileSystemOptions.h>
   9 #include <clang/Basic/FileManager.h>
  10 #include <clang/Basic/TargetOptions.h>
  11 #include <clang/Basic/TargetInfo.h>
  12 #include <clang/Frontend/CompilerInstance.h>
  13 #include <clang/Frontend/CompilerInvocation.h>
  14 #include <clang/Frontend/DiagnosticOptions.h>
  15 #include <clang/Frontend/TextDiagnosticPrinter.h>
  16 #include <clang/Frontend/HeaderSearchOptions.h>
  17 #include <clang/Frontend/LangStandard.h>
  18 #include <clang/Frontend/PreprocessorOptions.h>
  19 #include <clang/Frontend/FrontendOptions.h>
  20 #include <clang/Frontend/Utils.h>
  21 #include <clang/Lex/HeaderSearch.h>
  22 #include <clang/Lex/Preprocessor.h>
  23 #include <clang/Lex/Pragma.h>
  24 #include <clang/AST/ASTContext.h>
  25 #include <clang/AST/ASTConsumer.h>
  26 #include <clang/Sema/Sema.h>
  27 #include <clang/Sema/SemaDiagnostic.h>
  28 #include <clang/Parse/Parser.h>
  29 #include <clang/Parse/ParseAST.h>
  30
  31 #include <isl/ctx.h>
  32 #include <isl/constraint.h>
  33
  34 #include "scan.h"
  35
  36 #include "config.h"
  37
  38 #define ARRAY_SIZE(array) (sizeof(array)/sizeof(*array))
  39
  40 using namespace std;
  41 using namespace clang;
  42
  43 /* Called if we found something we didn't expect in one of the pragmas.
  44  * We'll provide more informative warnings later.
  45  */
  46 static void unsupported(Preprocessor &PP, SourceLocation loc)
  47 {
  48         Diagnostic &diag = PP.getDiagnostics();
  49         unsigned id = diag.getCustomDiagID(Diagnostic::Warning, "unsupported");
  50         DiagnosticBuilder B = diag.Report(loc, id);
  51 }
  52
  53 /* Set the lower and upper bounds on the given dimension of "set"
  54  * to "lb" and "ub".
  55  */
  56 static __isl_give isl_set *set_bounds(__isl_take isl_set *set,
  57         enum isl_dim_type type, int pos, int lb, int ub)
  58 {
  59         isl_constraint *c;
  60
  61         c = isl_inequality_alloc(isl_set_get_space(set));
  62         isl_constraint_set_coefficient_si(c, type, pos, 1);
  63         isl_constraint_set_constant_si(c, -lb);
  64         set = isl_set_add_constraint(set, c);
  65
  66         c = isl_inequality_alloc(isl_set_get_space(set));
  67         isl_constraint_set_coefficient_si(c, type, pos, -1);
  68         isl_constraint_set_constant_si(c, ub);
  69         set = isl_set_add_constraint(set, c);
  70
  71         return set;
  72 }
  73
  74 static int get_int(const char *s)
  75 {
  76         return s[0] == '"' ? atoi(s + 1) : atoi(s);
  77 }
  78
  79 static ValueDecl *get_value_decl(Sema &sema, Token &token)
  80 {
  81         IdentifierInfo *name;
  82         Decl *decl;
  83
  84         if (token.isNot(tok::identifier))
  85                 return NULL;
  86
  87         name = token.getIdentifierInfo();
  88         decl = sema.LookupSingleName(sema.TUScope, name,
  89                                 token.getLocation(), Sema::LookupOrdinaryName);
  90         return decl ? cast_or_null<ValueDecl>(decl) : NULL;
  91 }
  92
  93 /* Handle pragmas of the form
  94  *
  95  *      #pragma value_bounds identifier lower_bound upper_bound
  96  *
  97  * For each such pragma, add a mapping from the ValueDecl corresponding
  98  * to "identifier" to a set { [i] : lower_bound <= i <= upper_bound }
  99  * to the map value_bounds.
 100  */
 101 struct PragmaValueBoundsHandler : public PragmaHandler {
 102         Sema &sema;
 103         isl_ctx *ctx;
 104         map<ValueDecl *, isl_set *> &value_bounds;
 105
 106         PragmaValueBoundsHandler(isl_ctx *ctx, Sema &sema,
 107                                 map<ValueDecl *, isl_set *> &value_bounds) :
 108                 PragmaHandler("value_bounds"), ctx(ctx), sema(sema),
 109                 value_bounds(value_bounds) {}
 110
 111         virtual void HandlePragma(Preprocessor &PP,
 112                                   PragmaIntroducerKind Introducer,
 113                                   Token &ScopTok) {
 114                 isl_space *dim;
 115                 isl_set *set;
 116                 ValueDecl *vd;
 117                 Token token;
 118                 int lb;
 119                 int ub;
 120
 121                 PP.Lex(token);
 122                 vd = get_value_decl(sema, token);
 123                 if (!vd) {
 124                         unsupported(PP, token.getLocation());
 125                         return;
 126                 }
 127
 128                 PP.Lex(token);
 129                 if (!token.isLiteral()) {
 130                         unsupported(PP, token.getLocation());
 131                         return;
 132                 }
 133
 134                 lb = get_int(token.getLiteralData());
 135
 136                 PP.Lex(token);
 137                 if (!token.isLiteral()) {
 138                         unsupported(PP, token.getLocation());
 139                         return;
 140                 }
 141
 142                 ub = get_int(token.getLiteralData());
 143
 144                 dim = isl_space_set_alloc(ctx, 0, 1);
 145                 set = isl_set_universe(dim);
 146                 set = set_bounds(set, isl_dim_set, 0, lb, ub);
 147
 148                 value_bounds[vd] = set;
 149         }
 150 };
 151
 152 /* Handle pragmas of the form
 153  *
 154  *      #pragma parameter identifier lower_bound upper_bound
 155  *
 156  * For each such pragma, intersect the context with the set
 157  * [identifier] -> { [] : lower_bound <= identifier <= upper_bound }
 158  */
 159 struct PragmaParameterHandler : public PragmaHandler {
 160         Sema &sema;
 161         isl_set *&context;
 162
 163         PragmaParameterHandler(Sema &sema, isl_set *&context) :
 164                 PragmaHandler("parameter"), sema(sema), context(context) {}
 165
 166         virtual void HandlePragma(Preprocessor &PP,
 167                                   PragmaIntroducerKind Introducer,
 168                                   Token &ScopTok) {
 169                 isl_id *id;
 170                 isl_ctx *ctx = isl_set_get_ctx(context);
 171                 isl_space *dim;
 172                 isl_set *set;
 173                 ValueDecl *vd;
 174                 Token token;
 175                 int lb;
 176                 int ub;
 177
 178                 PP.Lex(token);
 179                 vd = get_value_decl(sema, token);
 180                 if (!vd) {
 181                         unsupported(PP, token.getLocation());
 182                         return;
 183                 }
 184
 185                 PP.Lex(token);
 186                 if (!token.isLiteral()) {
 187                         unsupported(PP, token.getLocation());
 188                         return;
 189                 }
 190
 191                 lb = get_int(token.getLiteralData());
 192
 193                 PP.Lex(token);
 194                 if (!token.isLiteral()) {
 195                         unsupported(PP, token.getLocation());
 196                         return;
 197                 }
 198
 199                 ub = get_int(token.getLiteralData());
 200
 201                 id = isl_id_alloc(ctx, vd->getName().str().c_str(), vd);
 202                 dim = isl_space_set_alloc(ctx, 1, 0);
 203                 dim = isl_space_set_dim_id(dim, isl_dim_param, 0, id);
 204
 205                 set = isl_set_universe(dim);
 206
 207                 set = set_bounds(set, isl_dim_param, 0, lb, ub);
 208
 209                 context = isl_set_intersect(context, set);
 210         }
 211 };
 212
 213 /* Handle pragmas of the form
 214  *
 215  *      #pragma scop
 216  *
 217  * In particular, store the current location in loc.start.
 218  */
 219 struct PragmaScopHandler : public PragmaHandler {
 220         ScopLoc &loc;
 221
 222         PragmaScopHandler(ScopLoc &loc) : PragmaHandler("scop"), loc(loc) {}
 223
 224         virtual void HandlePragma(Preprocessor &PP,
 225                                   PragmaIntroducerKind Introducer,
 226                                   Token &ScopTok) {
 227                 SourceManager &SM = PP.getSourceManager();
 228                 loc.start = SM.getFileOffset(ScopTok.getLocation());
 229         }
 230 };
 231
 232 /* Handle pragmas of the form
 233  *
 234  *      #pragma endscop
 235  *
 236  * In particular, store the current location in loc.end.
 237  */
 238 struct PragmaEndScopHandler : public PragmaHandler {
 239         ScopLoc &loc;
 240
 241         PragmaEndScopHandler(ScopLoc &loc) :
 242                 PragmaHandler("endscop"), loc(loc) {}
 243
 244         virtual void HandlePragma(Preprocessor &PP,
 245                                   PragmaIntroducerKind Introducer,
 246                                   Token &EndScopTok) {
 247                 SourceManager &SM = PP.getSourceManager();
 248                 loc.end = SM.getFileOffset(EndScopTok.getLocation());
 249         }
 250 };
 251
 252 /* Handle pragmas of the form
 253  *
 254  *      #pragma live-out identifier, identifier, ...
 255  *
 256  * Each identifier on the line is stored in live_out.
 257  */
 258 struct PragmaLiveOutHandler : public PragmaHandler {
 259         Sema &sema;
 260         set<ValueDecl *> &live_out;
 261
 262         PragmaLiveOutHandler(Sema &sema, set<ValueDecl *> &live_out) :
 263                 PragmaHandler("live"), sema(sema), live_out(live_out) {}
 264
 265         virtual void HandlePragma(Preprocessor &PP,
 266                                   PragmaIntroducerKind Introducer,
 267                                   Token &ScopTok) {
 268                 Token token;
 269
 270                 PP.Lex(token);
 271                 if (token.isNot(tok::minus))
 272                         return;
 273                 PP.Lex(token);
 274                 if (token.isNot(tok::identifier) ||
 275                     !token.getIdentifierInfo()->isStr("out"))
 276                         return;
 277
 278                 PP.Lex(token);
 279                 while (token.isNot(tok::eod)) {
 280                         ValueDecl *vd;
 281
 282                         vd = get_value_decl(sema, token);
 283                         if (!vd) {
 284                                 unsupported(PP, token.getLocation());
 285                                 return;
 286                         }
 287                         live_out.insert(vd);
 288                         PP.Lex(token);
 289                         if (token.is(tok::comma))
 290                                 PP.Lex(token);
 291                 }
 292         }
 293 };
 294
 295 /* Extract a pet_scop from the appropriate function.
 296  * If "function" is not NULL, then we only extract a pet_scop if the
 297  * name of the function matches.
 298  * If "autodetect" is false, then we only extract if we have seen
 299  * scop and endscop pragmas and if these are situated inside the function
 300  * body.
 301  */
 302 struct PetASTConsumer : public ASTConsumer {
 303         Preprocessor &PP;
 304         ASTContext &ast_context;
 305         ScopLoc &loc;
 306         const char *function;
 307         bool autodetect;
 308         isl_ctx *ctx;
 309         struct pet_scop *scop;
 310
 311         PetASTConsumer(isl_ctx *ctx, Preprocessor &PP, ASTContext &ast_context,
 312                 ScopLoc &loc, const char *function, bool autodetect) :
 313                 ctx(ctx), PP(PP), ast_context(ast_context), loc(loc),
 314                 scop(NULL), function(function), autodetect(autodetect) { }
 315
 316         virtual void HandleTopLevelDecl(DeclGroupRef dg) {
 317                 DeclGroupRef::iterator it;
 318
 319                 if (scop)
 320                         return;
 321                 for (it = dg.begin(); it != dg.end(); ++it) {
 322                         FunctionDecl *fd = dyn_cast<clang::FunctionDecl>(*it);
 323                         if (!fd)
 324                                 continue;
 325                         if (!fd->hasBody())
 326                                 continue;
 327                         if (function &&
 328                             fd->getNameInfo().getAsString() != function)
 329                                 continue;
 330                         if (autodetect) {
 331                                 PetScan ps(ctx, PP, ast_context, loc, 1);
 332                                 scop = ps.scan(fd);
 333                                 if (scop)
 334                                         break;
 335                                 else
 336                                         continue;
 337                         }
 338                         if (!loc.end)
 339                                 continue;
 340                         SourceManager &SM = PP.getSourceManager();
 341                         if (SM.getFileOffset(fd->getLocStart()) > loc.end)
 342                                 continue;
 343                         if (SM.getFileOffset(fd->getLocEnd()) < loc.start)
 344                                 continue;
 345                         PetScan ps(ctx, PP, ast_context, loc, 0);
 346                         scop = ps.scan(fd);
 347                         break;
 348                 }
 349         }
 350 };
 351
 352 static const char *ResourceDir = CLANG_PREFIX"/lib/clang/"CLANG_VERSION_STRING;
 353
 354 static const char *implicit_functions[] = {
 355         "min", "max", "ceild", "floord"
 356 };
 357
 358 static bool is_implicit(const IdentifierInfo *ident)
 359 {
 360         const char *name = ident->getNameStart();
 361         for (int i = 0; i < ARRAY_SIZE(implicit_functions); ++i)
 362                 if (!strcmp(name, implicit_functions[i]))
 363                         return true;
 364         return false;
 365 }
 366
 367 /* Ignore implicit function declaration warnings on
 368  * "min", "max", "ceild" and "floord" as we detect and handle these
 369  * in PetScan.
 370  */
 371 struct MyDiagnosticPrinter : public TextDiagnosticPrinter {
 372         MyDiagnosticPrinter(const DiagnosticOptions &DO) :
 373                 TextDiagnosticPrinter(llvm::errs(), DO) {}
 374         virtual void HandleDiagnostic(Diagnostic::Level level,
 375                                         const DiagnosticInfo &info) {
 376                 if (info.getID() == diag::ext_implicit_function_decl &&
 377                     info.getNumArgs() == 1 &&
 378                     info.getArgKind(0) == Diagnostic::ak_identifierinfo &&
 379                     is_implicit(info.getArgIdentifier(0)))
 380                         /* ignore warning */;
 381                 else
 382                         TextDiagnosticPrinter::HandleDiagnostic(level, info);
 383         }
 384 };
 385
 386 static void update_arrays(struct pet_scop *scop,
 387         map<ValueDecl *, isl_set *> &value_bounds,
 388         set<ValueDecl *> &live_out)
 389 {
 390         map<ValueDecl *, isl_set *>::iterator vb_it;
 391         set<ValueDecl *>::iterator lo_it;
 392
 393         if (!scop)
 394                 return;
 395
 396         for (int i = 0; i < scop->n_array; ++i) {
 397                 isl_id *id;
 398                 ValueDecl *decl;
 399                 pet_array *array = scop->arrays[i];
 400
 401                 id = isl_set_get_tuple_id(array->extent);
 402                 decl = (ValueDecl *)isl_id_get_user(id);
 403                 isl_id_free(id);
 404
 405                 vb_it = value_bounds.find(decl);
 406                 if (vb_it != value_bounds.end())
 407                         array->value_bounds = isl_set_copy(vb_it->second);
 408
 409                 lo_it = live_out.find(decl);
 410                 if (lo_it != live_out.end())
 411                         array->live_out = 1;
 412         }
 413 }
 414
 415 /* Extract a pet_scop from the C source file called "filename".
 416  * If "function" is not NULL, extract the pet_scop from the function
 417  * with that name.
 418  * If "autodetect" is set, extract any pet_scop we can find.
 419  * Otherwise, extract the pet_scop from the region delimited
 420  * by "scop" and "endscop" pragmas.
 421  *
 422  * We first set up the clang parser and then try to extract the
 423  * pet_scop from the appropriate function in PetASTConsumer.
 424  * If we have found a pet_scop, we add the context and value_bounds
 425  * constraints specified through pragmas.
 426  */
 427 struct pet_scop *pet_scop_extract_from_C_source(isl_ctx *ctx,
 428         const char *filename, const char *function, int autodetect)
 429 {
 430         isl_space *dim;
 431         isl_set *context;
 432         set<ValueDecl *> live_out;
 433         map<ValueDecl *, isl_set *> value_bounds;
 434         map<ValueDecl *, isl_set *>::iterator vb_it;
 435
 436         CompilerInstance *Clang = new CompilerInstance();
 437         DiagnosticOptions DO;
 438         Clang->createDiagnostics(0, NULL, new MyDiagnosticPrinter(DO));
 439         Diagnostic &Diags = Clang->getDiagnostics();
 440         Diags.setSuppressSystemWarnings(true);
 441         Clang->createFileManager();
 442         Clang->createSourceManager(Clang->getFileManager());
 443         TargetOptions TO;
 444         TO.Triple = llvm::sys::getHostTriple();
 445         TargetInfo *target = TargetInfo::CreateTargetInfo(Diags, TO);
 446         Clang->setTarget(target);
 447         CompilerInvocation::setLangDefaults(Clang->getLangOpts(), IK_C,
 448                                             LangStandard::lang_unspecified);
 449         Clang->getHeaderSearchOpts().ResourceDir = ResourceDir;
 450         Clang->createPreprocessor();
 451         Preprocessor &PP = Clang->getPreprocessor();
 452
 453         ScopLoc loc;
 454
 455         const FileEntry *file = Clang->getFileManager().getFile(filename);
 456         if (!file)
 457                 isl_die(ctx, isl_error_unknown, "unable to open file",
 458                         return NULL);
 459         Clang->getSourceManager().createMainFileID(file);
 460
 461         Clang->createASTContext();
 462         PetASTConsumer consumer(ctx, PP, Clang->getASTContext(),
 463                                 loc, function, autodetect);
 464         Sema *sema = new Sema(PP, Clang->getASTContext(), consumer);
 465
 466         if (!autodetect) {
 467                 PP.AddPragmaHandler(new PragmaScopHandler(loc));
 468                 PP.AddPragmaHandler(new PragmaEndScopHandler(loc));
 469                 PP.AddPragmaHandler(new PragmaLiveOutHandler(*sema, live_out));
 470         }
 471
 472         dim = isl_space_params_alloc(ctx, 0);
 473         context = isl_set_universe(dim);
 474         PP.AddPragmaHandler(new PragmaParameterHandler(*sema, context));
 475         PP.AddPragmaHandler(new PragmaValueBoundsHandler(ctx, *sema, value_bounds));
 476
 477         Diags.getClient()->BeginSourceFile(Clang->getLangOpts(), &PP);
 478         ParseAST(*sema);
 479         Diags.getClient()->EndSourceFile();
 480
 481         delete sema;
 482         delete Clang;
 483         llvm::llvm_shutdown();
 484
 485         if (consumer.scop)
 486                 consumer.scop->context = isl_set_intersect(context,
 487                                                     consumer.scop->context);
 488         else
 489                 isl_set_free(context);
 490
 491         update_arrays(consumer.scop, value_bounds, live_out);
 492
 493         for (vb_it = value_bounds.begin(); vb_it != value_bounds.end(); vb_it++)
 494                 isl_set_free(vb_it->second);
 495
 496         return consumer.scop;
 497 }