src/v8/tools/gcmole/gcmole.cc

   1 // Copyright 2011 the V8 project authors. All rights reserved.
   2 // Redistribution and use in source and binary forms, with or without
   3 // modification, are permitted provided that the following conditions are
   4 // met:
   5 //
   6 //     * Redistributions of source code must retain the above copyright
   7 //       notice, this list of conditions and the following disclaimer.
   8 //     * Redistributions in binary form must reproduce the above
   9 //       copyright notice, this list of conditions and the following
  10 //       disclaimer in the documentation and/or other materials provided
  11 //       with the distribution.
  12 //     * Neither the name of Google Inc. nor the names of its
  13 //       contributors may be used to endorse or promote products derived
  14 //       from this software without specific prior written permission.
  15 //
  16 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  17 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  18 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  19 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  20 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  21 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  22 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  23 // DATA, 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 // This is clang plugin used by gcmole tool. See README for more details.
  29
  30 #include "clang/AST/AST.h"
  31 #include "clang/AST/ASTConsumer.h"
  32 #include "clang/AST/Mangle.h"
  33 #include "clang/AST/RecursiveASTVisitor.h"
  34 #include "clang/AST/StmtVisitor.h"
  35 #include "clang/Frontend/FrontendPluginRegistry.h"
  36 #include "clang/Frontend/CompilerInstance.h"
  37 #include "llvm/Support/raw_ostream.h"
  38
  39 #include <bitset>
  40 #include <fstream>
  41 #include <iostream>
  42 #include <map>
  43 #include <set>
  44 #include <stack>
  45
  46 namespace {
  47
  48 typedef std::string MangledName;
  49 typedef std::set<MangledName> CalleesSet;
  50
  51 static bool GetMangledName(clang::MangleContext* ctx,
  52                            const clang::NamedDecl* decl,
  53                            MangledName* result) {
  54   if (!llvm::isa<clang::CXXConstructorDecl>(decl) &&
  55       !llvm::isa<clang::CXXDestructorDecl>(decl)) {
  56     llvm::SmallVector<char, 512> output;
  57     llvm::raw_svector_ostream out(output);
  58     ctx->mangleName(decl, out);
  59     *result = out.str().str();
  60     return true;
  61   }
  62
  63   return false;
  64 }
  65
  66
  67 static bool InV8Namespace(const clang::NamedDecl* decl) {
  68   return decl->getQualifiedNameAsString().compare(0, 4, "v8::") == 0;
  69 }
  70
  71
  72 static std::string EXTERNAL("EXTERNAL");
  73 static std::string STATE_TAG("enum v8::internal::StateTag");
  74
  75 static bool IsExternalVMState(const clang::ValueDecl* var) {
  76   const clang::EnumConstantDecl* enum_constant =
  77       llvm::dyn_cast<clang::EnumConstantDecl>(var);
  78   if (enum_constant != NULL && enum_constant->getNameAsString() == EXTERNAL) {
  79     clang::QualType type = enum_constant->getType();
  80     return (type.getAsString() == STATE_TAG);
  81   }
  82
  83   return false;
  84 }
  85
  86
  87 struct Resolver {
  88   explicit Resolver(clang::ASTContext& ctx)
  89       : ctx_(ctx), decl_ctx_(ctx.getTranslationUnitDecl()) {
  90   }
  91
  92   Resolver(clang::ASTContext& ctx, clang::DeclContext* decl_ctx)
  93       : ctx_(ctx), decl_ctx_(decl_ctx) {
  94   }
  95
  96   clang::DeclarationName ResolveName(const char* n) {
  97     clang::IdentifierInfo* ident = &ctx_.Idents.get(n);
  98     return ctx_.DeclarationNames.getIdentifier(ident);
  99   }
 100
 101   Resolver ResolveNamespace(const char* n) {
 102     return Resolver(ctx_, Resolve<clang::NamespaceDecl>(n));
 103   }
 104
 105   template<typename T>
 106   T* Resolve(const char* n) {
 107     if (decl_ctx_ == NULL) return NULL;
 108
 109     clang::DeclContext::lookup_result result =
 110         decl_ctx_->lookup(ResolveName(n));
 111
 112     clang::DeclContext::lookup_iterator end = result.end();
 113     for (clang::DeclContext::lookup_iterator i = result.begin(); i != end;
 114          i++) {
 115       if (llvm::isa<T>(*i)) return llvm::cast<T>(*i);
 116     }
 117
 118     return NULL;
 119   }
 120
 121  private:
 122   clang::ASTContext& ctx_;
 123   clang::DeclContext* decl_ctx_;
 124 };
 125
 126
 127 class CalleesPrinter : public clang::RecursiveASTVisitor<CalleesPrinter> {
 128  public:
 129   explicit CalleesPrinter(clang::MangleContext* ctx) : ctx_(ctx) {
 130   }
 131
 132   virtual bool VisitCallExpr(clang::CallExpr* expr) {
 133     const clang::FunctionDecl* callee = expr->getDirectCallee();
 134     if (callee != NULL) AnalyzeFunction(callee);
 135     return true;
 136   }
 137
 138   virtual bool VisitDeclRefExpr(clang::DeclRefExpr* expr) {
 139     // If function mentions EXTERNAL VMState add artificial garbage collection
 140     // mark.
 141     if (IsExternalVMState(expr->getDecl())) AddCallee("CollectGarbage");
 142     return true;
 143   }
 144
 145   void AnalyzeFunction(const clang::FunctionDecl* f) {
 146     MangledName name;
 147     if (InV8Namespace(f) && GetMangledName(ctx_, f, &name)) {
 148       AddCallee(name);
 149
 150       const clang::FunctionDecl* body = NULL;
 151       if (f->hasBody(body) && !Analyzed(name)) {
 152         EnterScope(name);
 153         TraverseStmt(body->getBody());
 154         LeaveScope();
 155       }
 156     }
 157   }
 158
 159   typedef std::map<MangledName, CalleesSet* > Callgraph;
 160
 161   bool Analyzed(const MangledName& name) {
 162     return callgraph_[name] != NULL;
 163   }
 164
 165   void EnterScope(const MangledName& name) {
 166     CalleesSet* callees = callgraph_[name];
 167
 168     if (callees == NULL) {
 169       callgraph_[name] = callees = new CalleesSet();
 170     }
 171
 172     scopes_.push(callees);
 173   }
 174
 175   void LeaveScope() {
 176     scopes_.pop();
 177   }
 178
 179   void AddCallee(const MangledName& name) {
 180     if (!scopes_.empty()) scopes_.top()->insert(name);
 181   }
 182
 183   void PrintCallGraph() {
 184     for (Callgraph::const_iterator i = callgraph_.begin(), e = callgraph_.end();
 185          i != e;
 186          ++i) {
 187       std::cout << i->first << "\n";
 188
 189       CalleesSet* callees = i->second;
 190       for (CalleesSet::const_iterator j = callees->begin(), e = callees->end();
 191            j != e;
 192            ++j) {
 193         std::cout << "\t" << *j << "\n";
 194       }
 195     }
 196   }
 197
 198  private:
 199   clang::MangleContext* ctx_;
 200
 201   std::stack<CalleesSet* > scopes_;
 202   Callgraph callgraph_;
 203 };
 204
 205
 206 class FunctionDeclarationFinder
 207     : public clang::ASTConsumer,
 208       public clang::RecursiveASTVisitor<FunctionDeclarationFinder> {
 209  public:
 210   explicit FunctionDeclarationFinder(clang::DiagnosticsEngine& d,
 211                                      clang::SourceManager& sm,
 212                                      const std::vector<std::string>& args)
 213       : d_(d), sm_(sm) {}
 214
 215   virtual void HandleTranslationUnit(clang::ASTContext &ctx) {
 216     mangle_context_ = clang::ItaniumMangleContext::create(ctx, d_);
 217     callees_printer_ = new CalleesPrinter(mangle_context_);
 218
 219     TraverseDecl(ctx.getTranslationUnitDecl());
 220
 221     callees_printer_->PrintCallGraph();
 222   }
 223
 224   virtual bool VisitFunctionDecl(clang::FunctionDecl* decl) {
 225     callees_printer_->AnalyzeFunction(decl);
 226     return true;
 227   }
 228
 229  private:
 230   clang::DiagnosticsEngine& d_;
 231   clang::SourceManager& sm_;
 232   clang::MangleContext* mangle_context_;
 233
 234   CalleesPrinter* callees_printer_;
 235 };
 236
 237
 238 static bool loaded = false;
 239 static CalleesSet gc_suspects;
 240
 241
 242 static void LoadGCSuspects() {
 243   if (loaded) return;
 244
 245   std::ifstream fin("gcsuspects");
 246   std::string s;
 247
 248   while (fin >> s) gc_suspects.insert(s);
 249
 250   loaded = true;
 251 }
 252
 253
 254 static bool KnownToCauseGC(clang::MangleContext* ctx,
 255                            const clang::FunctionDecl* decl) {
 256   LoadGCSuspects();
 257
 258   if (!InV8Namespace(decl)) return false;
 259
 260   MangledName name;
 261   if (GetMangledName(ctx, decl, &name)) {
 262     return gc_suspects.find(name) != gc_suspects.end();
 263   }
 264
 265   return false;
 266 }
 267
 268
 269 static const int kNoEffect = 0;
 270 static const int kCausesGC = 1;
 271 static const int kRawDef = 2;
 272 static const int kRawUse = 4;
 273 static const int kAllEffects = kCausesGC | kRawDef | kRawUse;
 274
 275 class Environment;
 276
 277 class ExprEffect {
 278  public:
 279   bool hasGC() { return (effect_ & kCausesGC) != 0; }
 280   void setGC() { effect_ |= kCausesGC; }
 281
 282   bool hasRawDef() { return (effect_ & kRawDef) != 0; }
 283   void setRawDef() { effect_ |= kRawDef; }
 284
 285   bool hasRawUse() { return (effect_ & kRawUse) != 0; }
 286   void setRawUse() { effect_ |= kRawUse; }
 287
 288   static ExprEffect None() { return ExprEffect(kNoEffect, NULL); }
 289   static ExprEffect NoneWithEnv(Environment* env) {
 290     return ExprEffect(kNoEffect, env);
 291   }
 292   static ExprEffect RawUse() { return ExprEffect(kRawUse, NULL); }
 293
 294   static ExprEffect Merge(ExprEffect a, ExprEffect b);
 295   static ExprEffect MergeSeq(ExprEffect a, ExprEffect b);
 296   ExprEffect Define(const std::string& name);
 297
 298   Environment* env() {
 299     return reinterpret_cast<Environment*>(effect_ & ~kAllEffects);
 300   }
 301
 302   static ExprEffect GC() {
 303     return ExprEffect(kCausesGC, NULL);
 304   }
 305
 306  private:
 307   ExprEffect(int effect, Environment* env)
 308       : effect_((effect & kAllEffects) |
 309                 reinterpret_cast<intptr_t>(env)) { }
 310
 311   intptr_t effect_;
 312 };
 313
 314
 315 const std::string BAD_EXPR_MSG("Possible problem with evaluation order.");
 316 const std::string DEAD_VAR_MSG("Possibly dead variable.");
 317
 318
 319 class Environment {
 320  public:
 321   Environment() { }
 322
 323   static Environment Unreachable() {
 324     Environment env;
 325     env.live_.set();
 326     return env;
 327   }
 328
 329   static Environment Merge(const Environment& l,
 330                            const Environment& r) {
 331     return Environment(l, r);
 332   }
 333
 334   Environment ApplyEffect(ExprEffect effect) const {
 335     Environment out = effect.hasGC() ? Environment() : Environment(*this);
 336     if (effect.env() != NULL) out.live_ |= effect.env()->live_;
 337     return out;
 338   }
 339
 340   typedef std::map<std::string, int> SymbolTable;
 341
 342   bool IsAlive(const std::string& name) const {
 343     SymbolTable::iterator code = symbol_table_.find(name);
 344     if (code == symbol_table_.end()) return false;
 345     return live_[code->second];
 346   }
 347
 348   bool Equal(const Environment& env) {
 349     return live_ == env.live_;
 350   }
 351
 352   Environment Define(const std::string& name) const {
 353     return Environment(*this, SymbolToCode(name));
 354   }
 355
 356   void MDefine(const std::string& name) {
 357     live_.set(SymbolToCode(name));
 358   }
 359
 360   static int SymbolToCode(const std::string& name) {
 361     SymbolTable::iterator code = symbol_table_.find(name);
 362
 363     if (code == symbol_table_.end()) {
 364       int new_code = symbol_table_.size();
 365       symbol_table_.insert(std::make_pair(name, new_code));
 366       return new_code;
 367     }
 368
 369     return code->second;
 370   }
 371
 372   static void ClearSymbolTable() {
 373     std::vector<Environment*>::iterator end = envs_.end();
 374     for (std::vector<Environment*>::iterator i = envs_.begin();
 375          i != end;
 376          ++i) {
 377       delete *i;
 378     }
 379     envs_.clear();
 380     symbol_table_.clear();
 381   }
 382
 383   void Print() const {
 384     bool comma = false;
 385     std::cout << "{";
 386     SymbolTable::iterator end = symbol_table_.end();
 387     for (SymbolTable::iterator i = symbol_table_.begin();
 388          i != end;
 389          ++i) {
 390       if (live_[i->second]) {
 391         if (comma) std::cout << ", ";
 392         std::cout << i->first;
 393         comma = true;
 394       }
 395     }
 396     std::cout << "}";
 397   }
 398
 399   static Environment* Allocate(const Environment& env) {
 400     Environment* allocated_env = new Environment(env);
 401     envs_.push_back(allocated_env);
 402     return allocated_env;
 403   }
 404
 405  private:
 406   Environment(const Environment& l, const Environment& r)
 407       : live_(l.live_ & r.live_) {
 408   }
 409
 410   Environment(const Environment& l, int code)
 411       : live_(l.live_) {
 412     live_.set(code);
 413   }
 414
 415   static SymbolTable symbol_table_;
 416   static std::vector<Environment* > envs_;
 417
 418   static const int kMaxNumberOfLocals = 256;
 419   std::bitset<kMaxNumberOfLocals> live_;
 420
 421   friend class ExprEffect;
 422   friend class CallProps;
 423 };
 424
 425
 426 class CallProps {
 427  public:
 428   CallProps() : env_(NULL) { }
 429
 430   void SetEffect(int arg, ExprEffect in) {
 431     if (in.hasGC()) gc_.set(arg);
 432     if (in.hasRawDef()) raw_def_.set(arg);
 433     if (in.hasRawUse()) raw_use_.set(arg);
 434     if (in.env() != NULL) {
 435       if (env_ == NULL) env_ = in.env();
 436       env_->live_ |= in.env()->live_;
 437     }
 438   }
 439
 440   ExprEffect ComputeCumulativeEffect(bool result_is_raw) {
 441     ExprEffect out = ExprEffect::NoneWithEnv(env_);
 442     if (gc_.any()) out.setGC();
 443     if (raw_use_.any()) out.setRawUse();
 444     if (result_is_raw) out.setRawDef();
 445     return out;
 446   }
 447
 448   bool IsSafe() {
 449     if (!gc_.any()) return true;
 450     std::bitset<kMaxNumberOfArguments> raw = (raw_def_ | raw_use_);
 451     if (!raw.any()) return true;
 452     return gc_.count() == 1 && !((raw ^ gc_).any());
 453   }
 454
 455  private:
 456   static const int kMaxNumberOfArguments = 64;
 457   std::bitset<kMaxNumberOfArguments> raw_def_;
 458   std::bitset<kMaxNumberOfArguments> raw_use_;
 459   std::bitset<kMaxNumberOfArguments> gc_;
 460   Environment* env_;
 461 };
 462
 463
 464 Environment::SymbolTable Environment::symbol_table_;
 465 std::vector<Environment* > Environment::envs_;
 466
 467
 468 ExprEffect ExprEffect::Merge(ExprEffect a, ExprEffect b) {
 469   Environment* a_env = a.env();
 470   Environment* b_env = b.env();
 471   Environment* out = NULL;
 472   if (a_env != NULL && b_env != NULL) {
 473     out = Environment::Allocate(*a_env);
 474     out->live_ &= b_env->live_;
 475   }
 476   return ExprEffect(a.effect_ | b.effect_, out);
 477 }
 478
 479
 480 ExprEffect ExprEffect::MergeSeq(ExprEffect a, ExprEffect b) {
 481   Environment* a_env = b.hasGC() ? NULL : a.env();
 482   Environment* b_env = b.env();
 483   Environment* out = (b_env == NULL) ? a_env : b_env;
 484   if (a_env != NULL && b_env != NULL) {
 485     out = Environment::Allocate(*b_env);
 486     out->live_ |= a_env->live_;
 487   }
 488   return ExprEffect(a.effect_ | b.effect_, out);
 489 }
 490
 491
 492 ExprEffect ExprEffect::Define(const std::string& name) {
 493   Environment* e = env();
 494   if (e == NULL) {
 495     e = Environment::Allocate(Environment());
 496   }
 497   e->MDefine(name);
 498   return ExprEffect(effect_, e);
 499 }
 500
 501
 502 static std::string THIS ("this");
 503
 504
 505 class FunctionAnalyzer {
 506  public:
 507   FunctionAnalyzer(clang::MangleContext* ctx,
 508                    clang::DeclarationName handle_decl_name,
 509                    clang::CXXRecordDecl* object_decl,
 510                    clang::CXXRecordDecl* smi_decl, clang::DiagnosticsEngine& d,
 511                    clang::SourceManager& sm, bool dead_vars_analysis)
 512       : ctx_(ctx),
 513         handle_decl_name_(handle_decl_name),
 514         object_decl_(object_decl),
 515         smi_decl_(smi_decl),
 516         d_(d),
 517         sm_(sm),
 518         block_(NULL),
 519         dead_vars_analysis_(dead_vars_analysis) {}
 520
 521
 522   // --------------------------------------------------------------------------
 523   // Expressions
 524   // --------------------------------------------------------------------------
 525
 526   ExprEffect VisitExpr(clang::Expr* expr, const Environment& env) {
 527 #define VISIT(type)                                                         \
 528   do {                                                                      \
 529     clang::type* concrete_expr = llvm::dyn_cast_or_null<clang::type>(expr); \
 530     if (concrete_expr != NULL) {                                            \
 531       return Visit##type(concrete_expr, env);                               \
 532     }                                                                       \
 533   } while (0);
 534
 535     VISIT(AbstractConditionalOperator);
 536     VISIT(AddrLabelExpr);
 537     VISIT(ArraySubscriptExpr);
 538     VISIT(BinaryOperator);
 539     VISIT(BlockExpr);
 540     VISIT(CallExpr);
 541     VISIT(CastExpr);
 542     VISIT(CharacterLiteral);
 543     VISIT(ChooseExpr);
 544     VISIT(CompoundLiteralExpr);
 545     VISIT(CXXBindTemporaryExpr);
 546     VISIT(CXXBoolLiteralExpr);
 547     VISIT(CXXConstructExpr);
 548     VISIT(CXXDefaultArgExpr);
 549     VISIT(CXXDeleteExpr);
 550     VISIT(CXXDependentScopeMemberExpr);
 551     VISIT(CXXNewExpr);
 552     VISIT(CXXNoexceptExpr);
 553     VISIT(CXXNullPtrLiteralExpr);
 554     VISIT(CXXPseudoDestructorExpr);
 555     VISIT(CXXScalarValueInitExpr);
 556     VISIT(CXXThisExpr);
 557     VISIT(CXXThrowExpr);
 558     VISIT(CXXTypeidExpr);
 559     VISIT(CXXUnresolvedConstructExpr);
 560     VISIT(CXXUuidofExpr);
 561     VISIT(DeclRefExpr);
 562     VISIT(DependentScopeDeclRefExpr);
 563     VISIT(DesignatedInitExpr);
 564     VISIT(ExprWithCleanups);
 565     VISIT(ExtVectorElementExpr);
 566     VISIT(FloatingLiteral);
 567     VISIT(GNUNullExpr);
 568     VISIT(ImaginaryLiteral);
 569     VISIT(ImplicitValueInitExpr);
 570     VISIT(InitListExpr);
 571     VISIT(IntegerLiteral);
 572     VISIT(MemberExpr);
 573     VISIT(OffsetOfExpr);
 574     VISIT(OpaqueValueExpr);
 575     VISIT(OverloadExpr);
 576     VISIT(PackExpansionExpr);
 577     VISIT(ParenExpr);
 578     VISIT(ParenListExpr);
 579     VISIT(PredefinedExpr);
 580     VISIT(ShuffleVectorExpr);
 581     VISIT(SizeOfPackExpr);
 582     VISIT(StmtExpr);
 583     VISIT(StringLiteral);
 584     VISIT(SubstNonTypeTemplateParmPackExpr);
 585     VISIT(TypeTraitExpr);
 586     VISIT(UnaryOperator);
 587     VISIT(VAArgExpr);
 588 #undef VISIT
 589
 590     return ExprEffect::None();
 591   }
 592
 593 #define DECL_VISIT_EXPR(type)                                           \
 594   ExprEffect Visit##type (clang::type* expr, const Environment& env)
 595
 596 #define IGNORE_EXPR(type)                                               \
 597   ExprEffect Visit##type (clang::type* expr, const Environment& env) {  \
 598     return ExprEffect::None();                                          \
 599   }
 600
 601   IGNORE_EXPR(AddrLabelExpr);
 602   IGNORE_EXPR(BlockExpr);
 603   IGNORE_EXPR(CharacterLiteral);
 604   IGNORE_EXPR(ChooseExpr);
 605   IGNORE_EXPR(CompoundLiteralExpr);
 606   IGNORE_EXPR(CXXBoolLiteralExpr);
 607   IGNORE_EXPR(CXXDependentScopeMemberExpr);
 608   IGNORE_EXPR(CXXNullPtrLiteralExpr);
 609   IGNORE_EXPR(CXXPseudoDestructorExpr);
 610   IGNORE_EXPR(CXXScalarValueInitExpr);
 611   IGNORE_EXPR(CXXNoexceptExpr);
 612   IGNORE_EXPR(CXXTypeidExpr);
 613   IGNORE_EXPR(CXXUnresolvedConstructExpr);
 614   IGNORE_EXPR(CXXUuidofExpr);
 615   IGNORE_EXPR(DependentScopeDeclRefExpr);
 616   IGNORE_EXPR(DesignatedInitExpr);
 617   IGNORE_EXPR(ExtVectorElementExpr);
 618   IGNORE_EXPR(FloatingLiteral);
 619   IGNORE_EXPR(ImaginaryLiteral);
 620   IGNORE_EXPR(IntegerLiteral);
 621   IGNORE_EXPR(OffsetOfExpr);
 622   IGNORE_EXPR(ImplicitValueInitExpr);
 623   IGNORE_EXPR(PackExpansionExpr);
 624   IGNORE_EXPR(PredefinedExpr);
 625   IGNORE_EXPR(ShuffleVectorExpr);
 626   IGNORE_EXPR(SizeOfPackExpr);
 627   IGNORE_EXPR(StmtExpr);
 628   IGNORE_EXPR(StringLiteral);
 629   IGNORE_EXPR(SubstNonTypeTemplateParmPackExpr);
 630   IGNORE_EXPR(TypeTraitExpr);
 631   IGNORE_EXPR(VAArgExpr);
 632   IGNORE_EXPR(GNUNullExpr);
 633   IGNORE_EXPR(OverloadExpr);
 634
 635   DECL_VISIT_EXPR(CXXThisExpr) {
 636     return Use(expr, expr->getType(), THIS, env);
 637   }
 638
 639   DECL_VISIT_EXPR(AbstractConditionalOperator) {
 640     Environment after_cond = env.ApplyEffect(VisitExpr(expr->getCond(), env));
 641     return ExprEffect::Merge(VisitExpr(expr->getTrueExpr(), after_cond),
 642                              VisitExpr(expr->getFalseExpr(), after_cond));
 643   }
 644
 645   DECL_VISIT_EXPR(ArraySubscriptExpr) {
 646     clang::Expr* exprs[2] = {expr->getBase(), expr->getIdx()};
 647     return Par(expr, 2, exprs, env);
 648   }
 649
 650   bool IsRawPointerVar(clang::Expr* expr, std::string* var_name) {
 651     if (llvm::isa<clang::DeclRefExpr>(expr)) {
 652       *var_name =
 653           llvm::cast<clang::DeclRefExpr>(expr)->getDecl()->getNameAsString();
 654       return true;
 655     }
 656     return false;
 657   }
 658
 659   DECL_VISIT_EXPR(BinaryOperator) {
 660     clang::Expr* lhs = expr->getLHS();
 661     clang::Expr* rhs = expr->getRHS();
 662     clang::Expr* exprs[2] = {lhs, rhs};
 663
 664     switch (expr->getOpcode()) {
 665       case clang::BO_Comma:
 666         return Seq(expr, 2, exprs, env);
 667
 668       case clang::BO_LAnd:
 669       case clang::BO_LOr:
 670         return ExprEffect::Merge(VisitExpr(lhs, env), VisitExpr(rhs, env));
 671
 672       case clang::BO_Assign: {
 673         std::string var_name;
 674         if (IsRawPointerVar(lhs, &var_name)) {
 675           return VisitExpr(rhs, env).Define(var_name);
 676         }
 677         return Par(expr, 2, exprs, env);
 678       }
 679
 680       default:
 681         return Par(expr, 2, exprs, env);
 682     }
 683   }
 684
 685   DECL_VISIT_EXPR(CXXBindTemporaryExpr) {
 686     return VisitExpr(expr->getSubExpr(), env);
 687   }
 688
 689   DECL_VISIT_EXPR(CXXConstructExpr) {
 690     return VisitArguments<>(expr, env);
 691   }
 692
 693   DECL_VISIT_EXPR(CXXDefaultArgExpr) {
 694     return VisitExpr(expr->getExpr(), env);
 695   }
 696
 697   DECL_VISIT_EXPR(CXXDeleteExpr) {
 698     return VisitExpr(expr->getArgument(), env);
 699   }
 700
 701   DECL_VISIT_EXPR(CXXNewExpr) { return VisitExpr(expr->getInitializer(), env); }
 702
 703   DECL_VISIT_EXPR(ExprWithCleanups) {
 704     return VisitExpr(expr->getSubExpr(), env);
 705   }
 706
 707   DECL_VISIT_EXPR(CXXThrowExpr) {
 708     return VisitExpr(expr->getSubExpr(), env);
 709   }
 710
 711   DECL_VISIT_EXPR(InitListExpr) {
 712     return Seq(expr, expr->getNumInits(), expr->getInits(), env);
 713   }
 714
 715   DECL_VISIT_EXPR(MemberExpr) {
 716     return VisitExpr(expr->getBase(), env);
 717   }
 718
 719   DECL_VISIT_EXPR(OpaqueValueExpr) {
 720     return VisitExpr(expr->getSourceExpr(), env);
 721   }
 722
 723   DECL_VISIT_EXPR(ParenExpr) {
 724     return VisitExpr(expr->getSubExpr(), env);
 725   }
 726
 727   DECL_VISIT_EXPR(ParenListExpr) {
 728     return Par(expr, expr->getNumExprs(), expr->getExprs(), env);
 729   }
 730
 731   DECL_VISIT_EXPR(UnaryOperator) {
 732     // TODO We are treating all expressions that look like &raw_pointer_var
 733     //      as definitions of raw_pointer_var. This should be changed to
 734     //      recognize less generic pattern:
 735     //
 736     //         if (maybe_object->ToObject(&obj)) return maybe_object;
 737     //
 738     if (expr->getOpcode() == clang::UO_AddrOf) {
 739       std::string var_name;
 740       if (IsRawPointerVar(expr->getSubExpr(), &var_name)) {
 741         return ExprEffect::None().Define(var_name);
 742       }
 743     }
 744     return VisitExpr(expr->getSubExpr(), env);
 745   }
 746
 747   DECL_VISIT_EXPR(CastExpr) {
 748     return VisitExpr(expr->getSubExpr(), env);
 749   }
 750
 751   DECL_VISIT_EXPR(DeclRefExpr) {
 752     return Use(expr, expr->getDecl(), env);
 753   }
 754
 755   ExprEffect Par(clang::Expr* parent,
 756                  int n,
 757                  clang::Expr** exprs,
 758                  const Environment& env) {
 759     CallProps props;
 760
 761     for (int i = 0; i < n; ++i) {
 762       props.SetEffect(i, VisitExpr(exprs[i], env));
 763     }
 764
 765     if (!props.IsSafe()) ReportUnsafe(parent, BAD_EXPR_MSG);
 766
 767     return props.ComputeCumulativeEffect(IsRawPointerType(parent->getType()));
 768   }
 769
 770   ExprEffect Seq(clang::Stmt* parent,
 771                  int n,
 772                  clang::Expr** exprs,
 773                  const Environment& env) {
 774     ExprEffect out = ExprEffect::None();
 775     Environment out_env = env;
 776     for (int i = 0; i < n; ++i) {
 777       out = ExprEffect::MergeSeq(out, VisitExpr(exprs[i], out_env));
 778       out_env = out_env.ApplyEffect(out);
 779     }
 780     return out;
 781   }
 782
 783   ExprEffect Use(const clang::Expr* parent,
 784                  const clang::QualType& var_type,
 785                  const std::string& var_name,
 786                  const Environment& env) {
 787     if (IsRawPointerType(var_type)) {
 788       if (!env.IsAlive(var_name) && dead_vars_analysis_) {
 789         ReportUnsafe(parent, DEAD_VAR_MSG);
 790       }
 791       return ExprEffect::RawUse();
 792     }
 793     return ExprEffect::None();
 794   }
 795
 796   ExprEffect Use(const clang::Expr* parent,
 797                  const clang::ValueDecl* var,
 798                  const Environment& env) {
 799     if (IsExternalVMState(var)) {
 800       return ExprEffect::GC();
 801     }
 802     return Use(parent, var->getType(), var->getNameAsString(), env);
 803   }
 804
 805
 806   template<typename ExprType>
 807   ExprEffect VisitArguments(ExprType* call, const Environment& env) {
 808     CallProps props;
 809     VisitArguments<>(call, &props, env);
 810     if (!props.IsSafe()) ReportUnsafe(call, BAD_EXPR_MSG);
 811     return props.ComputeCumulativeEffect(IsRawPointerType(call->getType()));
 812   }
 813
 814   template<typename ExprType>
 815   void VisitArguments(ExprType* call,
 816                       CallProps* props,
 817                       const Environment& env) {
 818     for (unsigned arg = 0; arg < call->getNumArgs(); arg++) {
 819       props->SetEffect(arg + 1, VisitExpr(call->getArg(arg), env));
 820     }
 821   }
 822
 823
 824   ExprEffect VisitCallExpr(clang::CallExpr* call,
 825                            const Environment& env) {
 826     CallProps props;
 827
 828     clang::CXXMemberCallExpr* memcall =
 829         llvm::dyn_cast_or_null<clang::CXXMemberCallExpr>(call);
 830     if (memcall != NULL) {
 831       clang::Expr* receiver = memcall->getImplicitObjectArgument();
 832       props.SetEffect(0, VisitExpr(receiver, env));
 833     }
 834
 835     VisitArguments<>(call, &props, env);
 836
 837     if (!props.IsSafe()) ReportUnsafe(call, BAD_EXPR_MSG);
 838
 839     ExprEffect out =
 840         props.ComputeCumulativeEffect(IsRawPointerType(call->getType()));
 841
 842     clang::FunctionDecl* callee = call->getDirectCallee();
 843     if ((callee != NULL) && KnownToCauseGC(ctx_, callee)) {
 844       out.setGC();
 845     }
 846
 847     return out;
 848   }
 849
 850   // --------------------------------------------------------------------------
 851   // Statements
 852   // --------------------------------------------------------------------------
 853
 854   Environment VisitStmt(clang::Stmt* stmt, const Environment& env) {
 855 #define VISIT(type)                                                         \
 856   do {                                                                      \
 857     clang::type* concrete_stmt = llvm::dyn_cast_or_null<clang::type>(stmt); \
 858     if (concrete_stmt != NULL) {                                            \
 859       return Visit##type(concrete_stmt, env);                               \
 860     }                                                                       \
 861   } while (0);
 862
 863     if (clang::Expr* expr = llvm::dyn_cast_or_null<clang::Expr>(stmt)) {
 864       return env.ApplyEffect(VisitExpr(expr, env));
 865     }
 866
 867     VISIT(AsmStmt);
 868     VISIT(BreakStmt);
 869     VISIT(CompoundStmt);
 870     VISIT(ContinueStmt);
 871     VISIT(CXXCatchStmt);
 872     VISIT(CXXTryStmt);
 873     VISIT(DeclStmt);
 874     VISIT(DoStmt);
 875     VISIT(ForStmt);
 876     VISIT(GotoStmt);
 877     VISIT(IfStmt);
 878     VISIT(IndirectGotoStmt);
 879     VISIT(LabelStmt);
 880     VISIT(NullStmt);
 881     VISIT(ReturnStmt);
 882     VISIT(CaseStmt);
 883     VISIT(DefaultStmt);
 884     VISIT(SwitchStmt);
 885     VISIT(WhileStmt);
 886 #undef VISIT
 887
 888     return env;
 889   }
 890
 891 #define DECL_VISIT_STMT(type)                                           \
 892   Environment Visit##type (clang::type* stmt, const Environment& env)
 893
 894 #define IGNORE_STMT(type)                                               \
 895   Environment Visit##type (clang::type* stmt, const Environment& env) { \
 896     return env;                                                         \
 897   }
 898
 899   IGNORE_STMT(IndirectGotoStmt);
 900   IGNORE_STMT(NullStmt);
 901   IGNORE_STMT(AsmStmt);
 902
 903   // We are ignoring control flow for simplicity.
 904   IGNORE_STMT(GotoStmt);
 905   IGNORE_STMT(LabelStmt);
 906
 907   // We are ignoring try/catch because V8 does not use them.
 908   IGNORE_STMT(CXXCatchStmt);
 909   IGNORE_STMT(CXXTryStmt);
 910
 911   class Block {
 912    public:
 913     Block(const Environment& in,
 914           FunctionAnalyzer* owner)
 915         : in_(in),
 916           out_(Environment::Unreachable()),
 917           changed_(false),
 918           owner_(owner) {
 919       parent_ = owner_->EnterBlock(this);
 920     }
 921
 922     ~Block() {
 923       owner_->LeaveBlock(parent_);
 924     }
 925
 926     void MergeIn(const Environment& env) {
 927       Environment old_in = in_;
 928       in_ = Environment::Merge(in_, env);
 929       changed_ = !old_in.Equal(in_);
 930     }
 931
 932     bool changed() {
 933       if (changed_) {
 934         changed_ = false;
 935         return true;
 936       }
 937       return false;
 938     }
 939
 940     const Environment& in() {
 941       return in_;
 942     }
 943
 944     const Environment& out() {
 945       return out_;
 946     }
 947
 948     void MergeOut(const Environment& env) {
 949       out_ = Environment::Merge(out_, env);
 950     }
 951
 952     void Seq(clang::Stmt* a, clang::Stmt* b, clang::Stmt* c) {
 953       Environment a_out = owner_->VisitStmt(a, in());
 954       Environment b_out = owner_->VisitStmt(b, a_out);
 955       Environment c_out = owner_->VisitStmt(c, b_out);
 956       MergeOut(c_out);
 957     }
 958
 959     void Seq(clang::Stmt* a, clang::Stmt* b) {
 960       Environment a_out = owner_->VisitStmt(a, in());
 961       Environment b_out = owner_->VisitStmt(b, a_out);
 962       MergeOut(b_out);
 963     }
 964
 965     void Loop(clang::Stmt* a, clang::Stmt* b, clang::Stmt* c) {
 966       Seq(a, b, c);
 967       MergeIn(out());
 968     }
 969
 970     void Loop(clang::Stmt* a, clang::Stmt* b) {
 971       Seq(a, b);
 972       MergeIn(out());
 973     }
 974
 975
 976    private:
 977     Environment in_;
 978     Environment out_;
 979     bool changed_;
 980     FunctionAnalyzer* owner_;
 981     Block* parent_;
 982   };
 983
 984
 985   DECL_VISIT_STMT(BreakStmt) {
 986     block_->MergeOut(env);
 987     return Environment::Unreachable();
 988   }
 989
 990   DECL_VISIT_STMT(ContinueStmt) {
 991     block_->MergeIn(env);
 992     return Environment::Unreachable();
 993   }
 994
 995   DECL_VISIT_STMT(CompoundStmt) {
 996     Environment out = env;
 997     clang::CompoundStmt::body_iterator end = stmt->body_end();
 998     for (clang::CompoundStmt::body_iterator s = stmt->body_begin();
 999          s != end;
1000          ++s) {
1001       out = VisitStmt(*s, out);
1002     }
1003     return out;
1004   }
1005
1006   DECL_VISIT_STMT(WhileStmt) {
1007     Block block (env, this);
1008     do {
1009       block.Loop(stmt->getCond(), stmt->getBody());
1010     } while (block.changed());
1011     return block.out();
1012   }
1013
1014   DECL_VISIT_STMT(DoStmt) {
1015     Block block (env, this);
1016     do {
1017       block.Loop(stmt->getBody(), stmt->getCond());
1018     } while (block.changed());
1019     return block.out();
1020   }
1021
1022   DECL_VISIT_STMT(ForStmt) {
1023     Block block (VisitStmt(stmt->getInit(), env), this);
1024     do {
1025       block.Loop(stmt->getCond(),
1026                  stmt->getBody(),
1027                  stmt->getInc());
1028     } while (block.changed());
1029     return block.out();
1030   }
1031
1032   DECL_VISIT_STMT(IfStmt) {
1033     Environment cond_out = VisitStmt(stmt->getCond(), env);
1034     Environment then_out = VisitStmt(stmt->getThen(), cond_out);
1035     Environment else_out = VisitStmt(stmt->getElse(), cond_out);
1036     return Environment::Merge(then_out, else_out);
1037   }
1038
1039   DECL_VISIT_STMT(SwitchStmt) {
1040     Block block (env, this);
1041     block.Seq(stmt->getCond(), stmt->getBody());
1042     return block.out();
1043   }
1044
1045   DECL_VISIT_STMT(CaseStmt) {
1046     Environment in = Environment::Merge(env, block_->in());
1047     Environment after_lhs = VisitStmt(stmt->getLHS(), in);
1048     return VisitStmt(stmt->getSubStmt(), after_lhs);
1049   }
1050
1051   DECL_VISIT_STMT(DefaultStmt) {
1052     Environment in = Environment::Merge(env, block_->in());
1053     return VisitStmt(stmt->getSubStmt(), in);
1054   }
1055
1056   DECL_VISIT_STMT(ReturnStmt) {
1057     VisitExpr(stmt->getRetValue(), env);
1058     return Environment::Unreachable();
1059   }
1060
1061   const clang::TagType* ToTagType(const clang::Type* t) {
1062     if (t == NULL) {
1063       return NULL;
1064     } else if (llvm::isa<clang::TagType>(t)) {
1065       return llvm::cast<clang::TagType>(t);
1066     } else if (llvm::isa<clang::SubstTemplateTypeParmType>(t)) {
1067       return ToTagType(llvm::cast<clang::SubstTemplateTypeParmType>(t)
1068                            ->getReplacementType()
1069                            .getTypePtr());
1070     } else {
1071       return NULL;
1072     }
1073   }
1074
1075   bool IsDerivedFrom(clang::CXXRecordDecl* record,
1076                      clang::CXXRecordDecl* base) {
1077     return (record == base) || record->isDerivedFrom(base);
1078   }
1079
1080   bool IsRawPointerType(clang::QualType qtype) {
1081     const clang::PointerType* type =
1082         llvm::dyn_cast_or_null<clang::PointerType>(qtype.getTypePtrOrNull());
1083     if (type == NULL) return false;
1084
1085     const clang::TagType* pointee =
1086         ToTagType(type->getPointeeType().getTypePtr());
1087     if (pointee == NULL) return false;
1088
1089     clang::CXXRecordDecl* record =
1090         llvm::dyn_cast_or_null<clang::CXXRecordDecl>(pointee->getDecl());
1091     if (record == NULL) return false;
1092
1093     if (!InV8Namespace(record)) return false;
1094
1095     if (!record->hasDefinition()) return false;
1096
1097     record = record->getDefinition();
1098
1099     return IsDerivedFrom(record, object_decl_) &&
1100         !IsDerivedFrom(record, smi_decl_);
1101   }
1102
1103   Environment VisitDecl(clang::Decl* decl, const Environment& env) {
1104     if (clang::VarDecl* var = llvm::dyn_cast<clang::VarDecl>(decl)) {
1105       Environment out = var->hasInit() ? VisitStmt(var->getInit(), env) : env;
1106
1107       if (IsRawPointerType(var->getType())) {
1108         out = out.Define(var->getNameAsString());
1109       }
1110
1111       return out;
1112     }
1113     // TODO: handle other declarations?
1114     return env;
1115   }
1116
1117   DECL_VISIT_STMT(DeclStmt) {
1118     Environment out = env;
1119     clang::DeclStmt::decl_iterator end = stmt->decl_end();
1120     for (clang::DeclStmt::decl_iterator decl = stmt->decl_begin();
1121          decl != end;
1122          ++decl) {
1123       out = VisitDecl(*decl, out);
1124     }
1125     return out;
1126   }
1127
1128
1129   void DefineParameters(const clang::FunctionDecl* f,
1130                         Environment* env) {
1131     env->MDefine(THIS);
1132     clang::FunctionDecl::param_const_iterator end = f->param_end();
1133     for (clang::FunctionDecl::param_const_iterator p = f->param_begin();
1134          p != end;
1135          ++p) {
1136       env->MDefine((*p)->getNameAsString());
1137     }
1138   }
1139
1140
1141   void AnalyzeFunction(const clang::FunctionDecl* f) {
1142     const clang::FunctionDecl* body = NULL;
1143     if (f->hasBody(body)) {
1144       Environment env;
1145       DefineParameters(body, &env);
1146       VisitStmt(body->getBody(), env);
1147       Environment::ClearSymbolTable();
1148     }
1149   }
1150
1151   Block* EnterBlock(Block* block) {
1152     Block* parent = block_;
1153     block_ = block;
1154     return parent;
1155   }
1156
1157   void LeaveBlock(Block* block) {
1158     block_ = block;
1159   }
1160
1161  private:
1162   void ReportUnsafe(const clang::Expr* expr, const std::string& msg) {
1163     d_.Report(clang::FullSourceLoc(expr->getExprLoc(), sm_),
1164               d_.getCustomDiagID(clang::DiagnosticsEngine::Warning, "%0"))
1165         << msg;
1166   }
1167
1168
1169   clang::MangleContext* ctx_;
1170   clang::DeclarationName handle_decl_name_;
1171   clang::CXXRecordDecl* object_decl_;
1172   clang::CXXRecordDecl* smi_decl_;
1173
1174   clang::DiagnosticsEngine& d_;
1175   clang::SourceManager& sm_;
1176
1177   Block* block_;
1178   bool dead_vars_analysis_;
1179 };
1180
1181
1182 class ProblemsFinder : public clang::ASTConsumer,
1183                        public clang::RecursiveASTVisitor<ProblemsFinder> {
1184  public:
1185   ProblemsFinder(clang::DiagnosticsEngine& d, clang::SourceManager& sm,
1186                  const std::vector<std::string>& args)
1187       : d_(d), sm_(sm), dead_vars_analysis_(false) {
1188     for (unsigned i = 0; i < args.size(); ++i) {
1189       if (args[i] == "--dead-vars") {
1190         dead_vars_analysis_ = true;
1191       }
1192     }
1193   }
1194
1195   virtual void HandleTranslationUnit(clang::ASTContext &ctx) {
1196     Resolver r(ctx);
1197
1198     clang::CXXRecordDecl* object_decl =
1199         r.ResolveNamespace("v8").ResolveNamespace("internal").
1200             Resolve<clang::CXXRecordDecl>("Object");
1201
1202     clang::CXXRecordDecl* smi_decl =
1203         r.ResolveNamespace("v8").ResolveNamespace("internal").
1204             Resolve<clang::CXXRecordDecl>("Smi");
1205
1206     if (object_decl != NULL) object_decl = object_decl->getDefinition();
1207
1208     if (smi_decl != NULL) smi_decl = smi_decl->getDefinition();
1209
1210     if (object_decl != NULL && smi_decl != NULL) {
1211       function_analyzer_ = new FunctionAnalyzer(
1212           clang::ItaniumMangleContext::create(ctx, d_), r.ResolveName("Handle"),
1213           object_decl, smi_decl, d_, sm_, dead_vars_analysis_);
1214       TraverseDecl(ctx.getTranslationUnitDecl());
1215     } else {
1216       if (object_decl == NULL) {
1217         llvm::errs() << "Failed to resolve v8::internal::Object\n";
1218       }
1219       if (smi_decl == NULL) {
1220         llvm::errs() << "Failed to resolve v8::internal::Smi\n";
1221       }
1222     }
1223   }
1224
1225   virtual bool VisitFunctionDecl(clang::FunctionDecl* decl) {
1226     function_analyzer_->AnalyzeFunction(decl);
1227     return true;
1228   }
1229
1230  private:
1231   clang::DiagnosticsEngine& d_;
1232   clang::SourceManager& sm_;
1233   bool dead_vars_analysis_;
1234
1235   FunctionAnalyzer* function_analyzer_;
1236 };
1237
1238
1239 template<typename ConsumerType>
1240 class Action : public clang::PluginASTAction {
1241  protected:
1242   clang::ASTConsumer *CreateASTConsumer(clang::CompilerInstance &CI,
1243                                         llvm::StringRef InFile) {
1244     return new ConsumerType(CI.getDiagnostics(), CI.getSourceManager(), args_);
1245   }
1246
1247   bool ParseArgs(const clang::CompilerInstance &CI,
1248                  const std::vector<std::string>& args) {
1249     args_ = args;
1250     return true;
1251   }
1252
1253   void PrintHelp(llvm::raw_ostream& ros) {
1254   }
1255  private:
1256   std::vector<std::string> args_;
1257 };
1258
1259
1260 }
1261
1262 static clang::FrontendPluginRegistry::Add<Action<ProblemsFinder> >
1263 FindProblems("find-problems", "Find GC-unsafe places.");
1264
1265 static clang::FrontendPluginRegistry::Add<
1266   Action<FunctionDeclarationFinder> >
1267 DumpCallees("dump-callees", "Dump callees for each function.");