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
46namespace {
47
48typedef std::string MangledName;
49typedef std::set<MangledName> CalleesSet;
50
51static 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
67static bool InV8Namespace(const clang::NamedDecl* decl) {
68  return decl->getQualifiedNameAsString().compare(0, 4, "v8::") == 0;
69}
70
71
72static std::string EXTERNAL("EXTERNAL");
73static std::string STATE_TAG("enum v8::internal::StateTag");
74
75static 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
87struct 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
127class 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
206class 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
238static bool loaded = false;
239static CalleesSet gc_suspects;
240
241
242static 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
254static 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
269static const int kNoEffect = 0;
270static const int kCausesGC = 1;
271static const int kRawDef = 2;
272static const int kRawUse = 4;
273static const int kAllEffects = kCausesGC | kRawDef | kRawUse;
274
275class Environment;
276
277class 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
315const std::string BAD_EXPR_MSG("Possible problem with evaluation order.");
316const std::string DEAD_VAR_MSG("Possibly dead variable.");
317
318
319class 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
426class 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
464Environment::SymbolTable Environment::symbol_table_;
465std::vector<Environment* > Environment::envs_;
466
467
468ExprEffect 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
480ExprEffect 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
492ExprEffect 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
502static std::string THIS ("this");
503
504
505class 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
1182class 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
1239template<typename ConsumerType>
1240class 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
1262static clang::FrontendPluginRegistry::Add<Action<ProblemsFinder> >
1263FindProblems("find-problems", "Find GC-unsafe places.");
1264
1265static clang::FrontendPluginRegistry::Add<
1266  Action<FunctionDeclarationFinder> >
1267DumpCallees("dump-callees", "Dump callees for each function.");
1268