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