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 (!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
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      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.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
128class 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
207class 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
239static bool loaded = false;
240static CalleesSet gc_suspects;
241
242
243static 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
255static 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
270static const int kNoEffect = 0;
271static const int kCausesGC = 1;
272static const int kRawDef = 2;
273static const int kRawUse = 4;
274static const int kAllEffects = kCausesGC | kRawDef | kRawUse;
275
276class Environment;
277
278class 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
316const std::string BAD_EXPR_MSG("Possible problem with evaluation order.");
317const std::string DEAD_VAR_MSG("Possibly dead variable.");
318
319
320class 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
427class 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
465Environment::SymbolTable Environment::symbol_table_;
466std::vector<Environment* > Environment::envs_;
467
468
469ExprEffect 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
481ExprEffect 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
493ExprEffect 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
503static std::string THIS ("this");
504
505
506class 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(UnaryExprOrTypeTraitExpr);
591    VISIT(UnaryOperator);
592    VISIT(UnaryTypeTraitExpr);
593    VISIT(VAArgExpr);
594#undef VISIT
595
596    return ExprEffect::None();
597  }
598
599#define DECL_VISIT_EXPR(type)                                           \
600  ExprEffect Visit##type (clang::type* expr, const Environment& env)
601
602#define IGNORE_EXPR(type)                                               \
603  ExprEffect Visit##type (clang::type* expr, const Environment& env) {  \
604    return ExprEffect::None();                                          \
605  }
606
607  IGNORE_EXPR(AddrLabelExpr);
608  IGNORE_EXPR(BinaryTypeTraitExpr);
609  IGNORE_EXPR(BlockExpr);
610  IGNORE_EXPR(CharacterLiteral);
611  IGNORE_EXPR(ChooseExpr);
612  IGNORE_EXPR(CompoundLiteralExpr);
613  IGNORE_EXPR(CXXBoolLiteralExpr);
614  IGNORE_EXPR(CXXDependentScopeMemberExpr);
615  IGNORE_EXPR(CXXNullPtrLiteralExpr);
616  IGNORE_EXPR(CXXPseudoDestructorExpr);
617  IGNORE_EXPR(CXXScalarValueInitExpr);
618  IGNORE_EXPR(CXXNoexceptExpr);
619  IGNORE_EXPR(CXXTypeidExpr);
620  IGNORE_EXPR(CXXUnresolvedConstructExpr);
621  IGNORE_EXPR(CXXUuidofExpr);
622  IGNORE_EXPR(DependentScopeDeclRefExpr);
623  IGNORE_EXPR(DesignatedInitExpr);
624  IGNORE_EXPR(ExtVectorElementExpr);
625  IGNORE_EXPR(FloatingLiteral);
626  IGNORE_EXPR(ImaginaryLiteral);
627  IGNORE_EXPR(IntegerLiteral);
628  IGNORE_EXPR(OffsetOfExpr);
629  IGNORE_EXPR(ImplicitValueInitExpr);
630  IGNORE_EXPR(PackExpansionExpr);
631  IGNORE_EXPR(PredefinedExpr);
632  IGNORE_EXPR(ShuffleVectorExpr);
633  IGNORE_EXPR(SizeOfPackExpr);
634  IGNORE_EXPR(StmtExpr);
635  IGNORE_EXPR(StringLiteral);
636  IGNORE_EXPR(SubstNonTypeTemplateParmPackExpr);
637  IGNORE_EXPR(UnaryExprOrTypeTraitExpr);
638  IGNORE_EXPR(UnaryTypeTraitExpr);
639  IGNORE_EXPR(VAArgExpr);
640  IGNORE_EXPR(GNUNullExpr);
641  IGNORE_EXPR(OverloadExpr);
642
643  DECL_VISIT_EXPR(CXXThisExpr) {
644    return Use(expr, expr->getType(), THIS, env);
645  }
646
647  DECL_VISIT_EXPR(AbstractConditionalOperator) {
648    Environment after_cond = env.ApplyEffect(VisitExpr(expr->getCond(), env));
649    return ExprEffect::Merge(VisitExpr(expr->getTrueExpr(), after_cond),
650                             VisitExpr(expr->getFalseExpr(), after_cond));
651  }
652
653  DECL_VISIT_EXPR(ArraySubscriptExpr) {
654    clang::Expr* exprs[2] = {expr->getBase(), expr->getIdx()};
655    return Par(expr, 2, exprs, env);
656  }
657
658  bool IsRawPointerVar(clang::Expr* expr, std::string* var_name) {
659    if (isa<clang::BlockDeclRefExpr>(expr)) {
660      *var_name = cast<clang::BlockDeclRefExpr>(expr)->getDecl()->
661          getNameAsString();
662      return true;
663    } else if (isa<clang::DeclRefExpr>(expr)) {
664      *var_name = cast<clang::DeclRefExpr>(expr)->getDecl()->getNameAsString();
665      return true;
666    }
667    return false;
668  }
669
670  DECL_VISIT_EXPR(BinaryOperator) {
671    clang::Expr* lhs = expr->getLHS();
672    clang::Expr* rhs = expr->getRHS();
673    clang::Expr* exprs[2] = {lhs, rhs};
674
675    switch (expr->getOpcode()) {
676      case clang::BO_Comma:
677        return Seq(expr, 2, exprs, env);
678
679      case clang::BO_LAnd:
680      case clang::BO_LOr:
681        return ExprEffect::Merge(VisitExpr(lhs, env), VisitExpr(rhs, env));
682
683      case clang::BO_Assign: {
684        std::string var_name;
685        if (IsRawPointerVar(lhs, &var_name)) {
686          return VisitExpr(rhs, env).Define(var_name);
687        }
688        return Par(expr, 2, exprs, env);
689      }
690
691      default:
692        return Par(expr, 2, exprs, env);
693    }
694  }
695
696  DECL_VISIT_EXPR(CXXBindTemporaryExpr) {
697    return VisitExpr(expr->getSubExpr(), env);
698  }
699
700  DECL_VISIT_EXPR(CXXConstructExpr) {
701    return VisitArguments<>(expr, env);
702  }
703
704  DECL_VISIT_EXPR(CXXDefaultArgExpr) {
705    return VisitExpr(expr->getExpr(), env);
706  }
707
708  DECL_VISIT_EXPR(CXXDeleteExpr) {
709    return VisitExpr(expr->getArgument(), env);
710  }
711
712  DECL_VISIT_EXPR(CXXNewExpr) {
713    return Par(expr,
714               expr->getNumConstructorArgs(),
715               expr->getConstructorArgs(),
716               env);
717  }
718
719  DECL_VISIT_EXPR(ExprWithCleanups) {
720    return VisitExpr(expr->getSubExpr(), env);
721  }
722
723  DECL_VISIT_EXPR(CXXThrowExpr) {
724    return VisitExpr(expr->getSubExpr(), env);
725  }
726
727  DECL_VISIT_EXPR(InitListExpr) {
728    return Seq(expr, expr->getNumInits(), expr->getInits(), env);
729  }
730
731  DECL_VISIT_EXPR(MemberExpr) {
732    return VisitExpr(expr->getBase(), env);
733  }
734
735  DECL_VISIT_EXPR(OpaqueValueExpr) {
736    return VisitExpr(expr->getSourceExpr(), env);
737  }
738
739  DECL_VISIT_EXPR(ParenExpr) {
740    return VisitExpr(expr->getSubExpr(), env);
741  }
742
743  DECL_VISIT_EXPR(ParenListExpr) {
744    return Par(expr, expr->getNumExprs(), expr->getExprs(), env);
745  }
746
747  DECL_VISIT_EXPR(UnaryOperator) {
748    // TODO We are treating all expressions that look like &raw_pointer_var
749    //      as definitions of raw_pointer_var. This should be changed to
750    //      recognize less generic pattern:
751    //
752    //         if (maybe_object->ToObject(&obj)) return maybe_object;
753    //
754    if (expr->getOpcode() == clang::UO_AddrOf) {
755      std::string var_name;
756      if (IsRawPointerVar(expr->getSubExpr(), &var_name)) {
757        return ExprEffect::None().Define(var_name);
758      }
759    }
760    return VisitExpr(expr->getSubExpr(), env);
761  }
762
763  DECL_VISIT_EXPR(CastExpr) {
764    return VisitExpr(expr->getSubExpr(), env);
765  }
766
767  DECL_VISIT_EXPR(DeclRefExpr) {
768    return Use(expr, expr->getDecl(), env);
769  }
770
771  DECL_VISIT_EXPR(BlockDeclRefExpr) {
772    return Use(expr, expr->getDecl(), env);
773  }
774
775  ExprEffect Par(clang::Expr* parent,
776                 int n,
777                 clang::Expr** exprs,
778                 const Environment& env) {
779    CallProps props;
780
781    for (int i = 0; i < n; ++i) {
782      props.SetEffect(i, VisitExpr(exprs[i], env));
783    }
784
785    if (!props.IsSafe()) ReportUnsafe(parent, BAD_EXPR_MSG);
786
787    return props.ComputeCumulativeEffect(IsRawPointerType(parent->getType()));
788  }
789
790  ExprEffect Seq(clang::Stmt* parent,
791                 int n,
792                 clang::Expr** exprs,
793                 const Environment& env) {
794    ExprEffect out = ExprEffect::None();
795    Environment out_env = env;
796    for (int i = 0; i < n; ++i) {
797      out = ExprEffect::MergeSeq(out, VisitExpr(exprs[i], out_env));
798      out_env = out_env.ApplyEffect(out);
799    }
800    return out;
801  }
802
803  ExprEffect Use(const clang::Expr* parent,
804                 const clang::QualType& var_type,
805                 const std::string& var_name,
806                 const Environment& env) {
807    if (IsRawPointerType(var_type)) {
808      if (!env.IsAlive(var_name) && dead_vars_analysis_) {
809        ReportUnsafe(parent, DEAD_VAR_MSG);
810      }
811      return ExprEffect::RawUse();
812    }
813    return ExprEffect::None();
814  }
815
816  ExprEffect Use(const clang::Expr* parent,
817                 const clang::ValueDecl* var,
818                 const Environment& env) {
819    if (IsExternalVMState(var)) {
820      return ExprEffect::GC();
821    }
822    return Use(parent, var->getType(), var->getNameAsString(), env);
823  }
824
825
826  template<typename ExprType>
827  ExprEffect VisitArguments(ExprType* call, const Environment& env) {
828    CallProps props;
829    VisitArguments<>(call, &props, env);
830    if (!props.IsSafe()) ReportUnsafe(call, BAD_EXPR_MSG);
831    return props.ComputeCumulativeEffect(IsRawPointerType(call->getType()));
832  }
833
834  template<typename ExprType>
835  void VisitArguments(ExprType* call,
836                      CallProps* props,
837                      const Environment& env) {
838    for (unsigned arg = 0; arg < call->getNumArgs(); arg++) {
839      props->SetEffect(arg + 1, VisitExpr(call->getArg(arg), env));
840    }
841  }
842
843
844  ExprEffect VisitCallExpr(clang::CallExpr* call,
845                           const Environment& env) {
846    CallProps props;
847
848    clang::CXXMemberCallExpr* memcall =
849        dyn_cast_or_null<clang::CXXMemberCallExpr>(call);
850    if (memcall != NULL) {
851      clang::Expr* receiver = memcall->getImplicitObjectArgument();
852      props.SetEffect(0, VisitExpr(receiver, env));
853    }
854
855    VisitArguments<>(call, &props, env);
856
857    if (!props.IsSafe()) ReportUnsafe(call, BAD_EXPR_MSG);
858
859    ExprEffect out =
860        props.ComputeCumulativeEffect(IsRawPointerType(call->getType()));
861
862    clang::FunctionDecl* callee = call->getDirectCallee();
863    if ((callee != NULL) && KnownToCauseGC(ctx_, callee)) {
864      out.setGC();
865    }
866
867    return out;
868  }
869
870  // --------------------------------------------------------------------------
871  // Statements
872  // --------------------------------------------------------------------------
873
874  Environment VisitStmt(clang::Stmt* stmt, const Environment& env) {
875#define VISIT(type) do {                                                \
876      clang::type* concrete_stmt = dyn_cast_or_null<clang::type>(stmt); \
877      if (concrete_stmt != NULL) {                                      \
878        return Visit##type (concrete_stmt, env);                        \
879      }                                                                 \
880    } while(0);
881
882    if (clang::Expr* expr = dyn_cast_or_null<clang::Expr>(stmt)) {
883      return env.ApplyEffect(VisitExpr(expr, env));
884    }
885
886    VISIT(AsmStmt);
887    VISIT(BreakStmt);
888    VISIT(CompoundStmt);
889    VISIT(ContinueStmt);
890    VISIT(CXXCatchStmt);
891    VISIT(CXXTryStmt);
892    VISIT(DeclStmt);
893    VISIT(DoStmt);
894    VISIT(ForStmt);
895    VISIT(GotoStmt);
896    VISIT(IfStmt);
897    VISIT(IndirectGotoStmt);
898    VISIT(LabelStmt);
899    VISIT(NullStmt);
900    VISIT(ReturnStmt);
901    VISIT(CaseStmt);
902    VISIT(DefaultStmt);
903    VISIT(SwitchStmt);
904    VISIT(WhileStmt);
905#undef VISIT
906
907    return env;
908  }
909
910#define DECL_VISIT_STMT(type)                                           \
911  Environment Visit##type (clang::type* stmt, const Environment& env)
912
913#define IGNORE_STMT(type)                                               \
914  Environment Visit##type (clang::type* stmt, const Environment& env) { \
915    return env;                                                         \
916  }
917
918  IGNORE_STMT(IndirectGotoStmt);
919  IGNORE_STMT(NullStmt);
920  IGNORE_STMT(AsmStmt);
921
922  // We are ignoring control flow for simplicity.
923  IGNORE_STMT(GotoStmt);
924  IGNORE_STMT(LabelStmt);
925
926  // We are ignoring try/catch because V8 does not use them.
927  IGNORE_STMT(CXXCatchStmt);
928  IGNORE_STMT(CXXTryStmt);
929
930  class Block {
931   public:
932    Block(const Environment& in,
933          FunctionAnalyzer* owner)
934        : in_(in),
935          out_(Environment::Unreachable()),
936          changed_(false),
937          owner_(owner) {
938      parent_ = owner_->EnterBlock(this);
939    }
940
941    ~Block() {
942      owner_->LeaveBlock(parent_);
943    }
944
945    void MergeIn(const Environment& env) {
946      Environment old_in = in_;
947      in_ = Environment::Merge(in_, env);
948      changed_ = !old_in.Equal(in_);
949    }
950
951    bool changed() {
952      if (changed_) {
953        changed_ = false;
954        return true;
955      }
956      return false;
957    }
958
959    const Environment& in() {
960      return in_;
961    }
962
963    const Environment& out() {
964      return out_;
965    }
966
967    void MergeOut(const Environment& env) {
968      out_ = Environment::Merge(out_, env);
969    }
970
971    void Seq(clang::Stmt* a, clang::Stmt* b, clang::Stmt* c) {
972      Environment a_out = owner_->VisitStmt(a, in());
973      Environment b_out = owner_->VisitStmt(b, a_out);
974      Environment c_out = owner_->VisitStmt(c, b_out);
975      MergeOut(c_out);
976    }
977
978    void Seq(clang::Stmt* a, clang::Stmt* b) {
979      Environment a_out = owner_->VisitStmt(a, in());
980      Environment b_out = owner_->VisitStmt(b, a_out);
981      MergeOut(b_out);
982    }
983
984    void Loop(clang::Stmt* a, clang::Stmt* b, clang::Stmt* c) {
985      Seq(a, b, c);
986      MergeIn(out());
987    }
988
989    void Loop(clang::Stmt* a, clang::Stmt* b) {
990      Seq(a, b);
991      MergeIn(out());
992    }
993
994
995   private:
996    Environment in_;
997    Environment out_;
998    bool changed_;
999    FunctionAnalyzer* owner_;
1000    Block* parent_;
1001  };
1002
1003
1004  DECL_VISIT_STMT(BreakStmt) {
1005    block_->MergeOut(env);
1006    return Environment::Unreachable();
1007  }
1008
1009  DECL_VISIT_STMT(ContinueStmt) {
1010    block_->MergeIn(env);
1011    return Environment::Unreachable();
1012  }
1013
1014  DECL_VISIT_STMT(CompoundStmt) {
1015    Environment out = env;
1016    clang::CompoundStmt::body_iterator end = stmt->body_end();
1017    for (clang::CompoundStmt::body_iterator s = stmt->body_begin();
1018         s != end;
1019         ++s) {
1020      out = VisitStmt(*s, out);
1021    }
1022    return out;
1023  }
1024
1025  DECL_VISIT_STMT(WhileStmt) {
1026    Block block (env, this);
1027    do {
1028      block.Loop(stmt->getCond(), stmt->getBody());
1029    } while (block.changed());
1030    return block.out();
1031  }
1032
1033  DECL_VISIT_STMT(DoStmt) {
1034    Block block (env, this);
1035    do {
1036      block.Loop(stmt->getBody(), stmt->getCond());
1037    } while (block.changed());
1038    return block.out();
1039  }
1040
1041  DECL_VISIT_STMT(ForStmt) {
1042    Block block (VisitStmt(stmt->getInit(), env), this);
1043    do {
1044      block.Loop(stmt->getCond(),
1045                 stmt->getBody(),
1046                 stmt->getInc());
1047    } while (block.changed());
1048    return block.out();
1049  }
1050
1051  DECL_VISIT_STMT(IfStmt) {
1052    Environment cond_out = VisitStmt(stmt->getCond(), env);
1053    Environment then_out = VisitStmt(stmt->getThen(), cond_out);
1054    Environment else_out = VisitStmt(stmt->getElse(), cond_out);
1055    return Environment::Merge(then_out, else_out);
1056  }
1057
1058  DECL_VISIT_STMT(SwitchStmt) {
1059    Block block (env, this);
1060    block.Seq(stmt->getCond(), stmt->getBody());
1061    return block.out();
1062  }
1063
1064  DECL_VISIT_STMT(CaseStmt) {
1065    Environment in = Environment::Merge(env, block_->in());
1066    Environment after_lhs = VisitStmt(stmt->getLHS(), in);
1067    return VisitStmt(stmt->getSubStmt(), after_lhs);
1068  }
1069
1070  DECL_VISIT_STMT(DefaultStmt) {
1071    Environment in = Environment::Merge(env, block_->in());
1072    return VisitStmt(stmt->getSubStmt(), in);
1073  }
1074
1075  DECL_VISIT_STMT(ReturnStmt) {
1076    VisitExpr(stmt->getRetValue(), env);
1077    return Environment::Unreachable();
1078  }
1079
1080  const clang::TagType* ToTagType(const clang::Type* t) {
1081    if (t == NULL) {
1082      return NULL;
1083    } else if (isa<clang::TagType>(t)) {
1084      return cast<clang::TagType>(t);
1085    } else if (isa<clang::SubstTemplateTypeParmType>(t)) {
1086      return ToTagType(cast<clang::SubstTemplateTypeParmType>(t)->
1087                           getReplacementType().getTypePtr());
1088    } else {
1089      return NULL;
1090    }
1091  }
1092
1093  bool IsDerivedFrom(clang::CXXRecordDecl* record,
1094                     clang::CXXRecordDecl* base) {
1095    return (record == base) || record->isDerivedFrom(base);
1096  }
1097
1098  bool IsRawPointerType(clang::QualType qtype) {
1099    const clang::PointerType* type =
1100        dyn_cast_or_null<clang::PointerType>(qtype.getTypePtrOrNull());
1101    if (type == NULL) return false;
1102
1103    const clang::TagType* pointee =
1104        ToTagType(type->getPointeeType().getTypePtr());
1105    if (pointee == NULL) return false;
1106
1107    clang::CXXRecordDecl* record =
1108        dyn_cast_or_null<clang::CXXRecordDecl>(pointee->getDecl());
1109    if (record == NULL) return false;
1110
1111    if (!InV8Namespace(record)) return false;
1112
1113    if (!record->hasDefinition()) return false;
1114
1115    record = record->getDefinition();
1116
1117    return IsDerivedFrom(record, object_decl_) &&
1118        !IsDerivedFrom(record, smi_decl_);
1119  }
1120
1121  Environment VisitDecl(clang::Decl* decl, const Environment& env) {
1122    if (clang::VarDecl* var = dyn_cast<clang::VarDecl>(decl)) {
1123      Environment out = var->hasInit() ? VisitStmt(var->getInit(), env) : env;
1124
1125      if (IsRawPointerType(var->getType())) {
1126        out = out.Define(var->getNameAsString());
1127      }
1128
1129      return out;
1130    }
1131    // TODO: handle other declarations?
1132    return env;
1133  }
1134
1135  DECL_VISIT_STMT(DeclStmt) {
1136    Environment out = env;
1137    clang::DeclStmt::decl_iterator end = stmt->decl_end();
1138    for (clang::DeclStmt::decl_iterator decl = stmt->decl_begin();
1139         decl != end;
1140         ++decl) {
1141      out = VisitDecl(*decl, out);
1142    }
1143    return out;
1144  }
1145
1146
1147  void DefineParameters(const clang::FunctionDecl* f,
1148                        Environment* env) {
1149    env->MDefine(THIS);
1150    clang::FunctionDecl::param_const_iterator end = f->param_end();
1151    for (clang::FunctionDecl::param_const_iterator p = f->param_begin();
1152         p != end;
1153         ++p) {
1154      env->MDefine((*p)->getNameAsString());
1155    }
1156  }
1157
1158
1159  void AnalyzeFunction(const clang::FunctionDecl* f) {
1160    const clang::FunctionDecl* body = NULL;
1161    if (f->hasBody(body)) {
1162      Environment env;
1163      DefineParameters(body, &env);
1164      VisitStmt(body->getBody(), env);
1165      Environment::ClearSymbolTable();
1166    }
1167  }
1168
1169  Block* EnterBlock(Block* block) {
1170    Block* parent = block_;
1171    block_ = block;
1172    return parent;
1173  }
1174
1175  void LeaveBlock(Block* block) {
1176    block_ = block;
1177  }
1178
1179 private:
1180  void ReportUnsafe(const clang::Expr* expr, const std::string& msg) {
1181    d_.Report(clang::FullSourceLoc(expr->getExprLoc(), sm_),
1182              d_.getCustomDiagID(clang::Diagnostic::Warning, msg));
1183  }
1184
1185
1186  clang::MangleContext* ctx_;
1187  clang::DeclarationName handle_decl_name_;
1188  clang::CXXRecordDecl* object_decl_;
1189  clang::CXXRecordDecl* smi_decl_;
1190
1191  clang::Diagnostic& d_;
1192  clang::SourceManager& sm_;
1193
1194  Block* block_;
1195  bool dead_vars_analysis_;
1196};
1197
1198
1199class ProblemsFinder : public clang::ASTConsumer,
1200                       public clang::RecursiveASTVisitor<ProblemsFinder> {
1201 public:
1202  ProblemsFinder(clang::Diagnostic& d,
1203                 clang::SourceManager& sm,
1204                 const std::vector<std::string>& args)
1205      : d_(d), sm_(sm), dead_vars_analysis_(false) {
1206    for (unsigned i = 0; i < args.size(); ++i) {
1207      if (args[i] == "--dead-vars") {
1208        dead_vars_analysis_ = true;
1209      }
1210    }
1211  }
1212
1213  virtual void HandleTranslationUnit(clang::ASTContext &ctx) {
1214    Resolver r(ctx);
1215
1216    clang::CXXRecordDecl* object_decl =
1217        r.ResolveNamespace("v8").ResolveNamespace("internal").
1218            Resolve<clang::CXXRecordDecl>("Object");
1219
1220    clang::CXXRecordDecl* smi_decl =
1221        r.ResolveNamespace("v8").ResolveNamespace("internal").
1222            Resolve<clang::CXXRecordDecl>("Smi");
1223
1224    if (object_decl != NULL) object_decl = object_decl->getDefinition();
1225
1226    if (smi_decl != NULL) smi_decl = smi_decl->getDefinition();
1227
1228    if (object_decl != NULL && smi_decl != NULL) {
1229      function_analyzer_ =
1230          new FunctionAnalyzer(clang::createItaniumMangleContext(ctx, d_),
1231                               r.ResolveName("Handle"),
1232                               object_decl,
1233                               smi_decl,
1234                               d_,
1235                               sm_,
1236                               dead_vars_analysis_);
1237      TraverseDecl(ctx.getTranslationUnitDecl());
1238    } else {
1239      if (object_decl == NULL) {
1240        llvm::errs() << "Failed to resolve v8::internal::Object\n";
1241      }
1242      if (smi_decl == NULL) {
1243        llvm::errs() << "Failed to resolve v8::internal::Smi\n";
1244      }
1245    }
1246  }
1247
1248  virtual bool VisitFunctionDecl(clang::FunctionDecl* decl) {
1249    function_analyzer_->AnalyzeFunction(decl);
1250    return true;
1251  }
1252
1253 private:
1254  clang::Diagnostic& d_;
1255  clang::SourceManager& sm_;
1256  bool dead_vars_analysis_;
1257
1258  FunctionAnalyzer* function_analyzer_;
1259};
1260
1261
1262template<typename ConsumerType>
1263class Action : public clang::PluginASTAction {
1264 protected:
1265  clang::ASTConsumer *CreateASTConsumer(clang::CompilerInstance &CI,
1266                                        llvm::StringRef InFile) {
1267    return new ConsumerType(CI.getDiagnostics(), CI.getSourceManager(), args_);
1268  }
1269
1270  bool ParseArgs(const clang::CompilerInstance &CI,
1271                 const std::vector<std::string>& args) {
1272    args_ = args;
1273    return true;
1274  }
1275
1276  void PrintHelp(llvm::raw_ostream& ros) {
1277  }
1278 private:
1279  std::vector<std::string> args_;
1280};
1281
1282
1283}
1284
1285static clang::FrontendPluginRegistry::Add<Action<ProblemsFinder> >
1286FindProblems("find-problems", "Find GC-unsafe places.");
1287
1288static clang::FrontendPluginRegistry::Add<
1289  Action<FunctionDeclarationFinder> >
1290DumpCallees("dump-callees", "Dump callees for each function.");
1291