gcmole.cc 35.8 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53
// Copyright 2011 the V8 project authors. All rights reserved.
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are
// met:
//
//     * Redistributions of source code must retain the above copyright
//       notice, this list of conditions and the following disclaimer.
//     * Redistributions in binary form must reproduce the above
//       copyright notice, this list of conditions and the following
//       disclaimer in the documentation and/or other materials provided
//       with the distribution.
//     * Neither the name of Google Inc. nor the names of its
//       contributors may be used to endorse or promote products derived
//       from this software without specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

// This is clang plugin used by gcmole tool. See README for more details.

#include "clang/AST/AST.h"
#include "clang/AST/ASTConsumer.h"
#include "clang/AST/Mangle.h"
#include "clang/AST/RecursiveASTVisitor.h"
#include "clang/AST/StmtVisitor.h"
#include "clang/Frontend/FrontendPluginRegistry.h"
#include "clang/Frontend/CompilerInstance.h"
#include "llvm/Support/raw_ostream.h"

#include <bitset>
#include <fstream>
#include <iostream>
#include <map>
#include <set>
#include <stack>

namespace {

typedef std::string MangledName;
typedef std::set<MangledName> CalleesSet;

static bool GetMangledName(clang::MangleContext* ctx,
                           const clang::NamedDecl* decl,
                           MangledName* result) {
54 55
  if (!llvm::isa<clang::CXXConstructorDecl>(decl) &&
      !llvm::isa<clang::CXXDestructorDecl>(decl)) {
56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71
    llvm::SmallVector<char, 512> output;
    llvm::raw_svector_ostream out(output);
    ctx->mangleName(decl, out);
    *result = out.str().str();
    return true;
  }

  return false;
}


static bool InV8Namespace(const clang::NamedDecl* decl) {
  return decl->getQualifiedNameAsString().compare(0, 4, "v8::") == 0;
}


72 73 74 75 76
static std::string EXTERNAL("EXTERNAL");
static std::string STATE_TAG("enum v8::internal::StateTag");

static bool IsExternalVMState(const clang::ValueDecl* var) {
  const clang::EnumConstantDecl* enum_constant =
77
      llvm::dyn_cast<clang::EnumConstantDecl>(var);
78 79 80 81 82 83 84 85 86
  if (enum_constant != NULL && enum_constant->getNameAsString() == EXTERNAL) {
    clang::QualType type = enum_constant->getType();
    return (type.getAsString() == STATE_TAG);
  }

  return false;
}


87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111
struct Resolver {
  explicit Resolver(clang::ASTContext& ctx)
      : ctx_(ctx), decl_ctx_(ctx.getTranslationUnitDecl()) {
  }

  Resolver(clang::ASTContext& ctx, clang::DeclContext* decl_ctx)
      : ctx_(ctx), decl_ctx_(decl_ctx) {
  }

  clang::DeclarationName ResolveName(const char* n) {
    clang::IdentifierInfo* ident = &ctx_.Idents.get(n);
    return ctx_.DeclarationNames.getIdentifier(ident);
  }

  Resolver ResolveNamespace(const char* n) {
    return Resolver(ctx_, Resolve<clang::NamespaceDecl>(n));
  }

  template<typename T>
  T* Resolve(const char* n) {
    if (decl_ctx_ == NULL) return NULL;

    clang::DeclContext::lookup_result result =
        decl_ctx_->lookup(ResolveName(n));

112 113
    clang::DeclContext::lookup_iterator end = result.end();
    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 119 120 121 122 123 124 125 126
    }

    return NULL;
  }

 private:
  clang::ASTContext& ctx_;
  clang::DeclContext* decl_ctx_;
};


127 128 129 130 131 132 133 134 135 136 137
class CalleesPrinter : public clang::RecursiveASTVisitor<CalleesPrinter> {
 public:
  explicit CalleesPrinter(clang::MangleContext* ctx) : ctx_(ctx) {
  }

  virtual bool VisitCallExpr(clang::CallExpr* expr) {
    const clang::FunctionDecl* callee = expr->getDirectCallee();
    if (callee != NULL) AnalyzeFunction(callee);
    return true;
  }

138 139 140 141 142 143 144
  virtual bool VisitDeclRefExpr(clang::DeclRefExpr* expr) {
    // If function mentions EXTERNAL VMState add artificial garbage collection
    // mark.
    if (IsExternalVMState(expr->getDecl())) AddCallee("CollectGarbage");
    return true;
  }

145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204
  void AnalyzeFunction(const clang::FunctionDecl* f) {
    MangledName name;
    if (InV8Namespace(f) && GetMangledName(ctx_, f, &name)) {
      AddCallee(name);

      const clang::FunctionDecl* body = NULL;
      if (f->hasBody(body) && !Analyzed(name)) {
        EnterScope(name);
        TraverseStmt(body->getBody());
        LeaveScope();
      }
    }
  }

  typedef std::map<MangledName, CalleesSet* > Callgraph;

  bool Analyzed(const MangledName& name) {
    return callgraph_[name] != NULL;
  }

  void EnterScope(const MangledName& name) {
    CalleesSet* callees = callgraph_[name];

    if (callees == NULL) {
      callgraph_[name] = callees = new CalleesSet();
    }

    scopes_.push(callees);
  }

  void LeaveScope() {
    scopes_.pop();
  }

  void AddCallee(const MangledName& name) {
    if (!scopes_.empty()) scopes_.top()->insert(name);
  }

  void PrintCallGraph() {
    for (Callgraph::const_iterator i = callgraph_.begin(), e = callgraph_.end();
         i != e;
         ++i) {
      std::cout << i->first << "\n";

      CalleesSet* callees = i->second;
      for (CalleesSet::const_iterator j = callees->begin(), e = callees->end();
           j != e;
           ++j) {
        std::cout << "\t" << *j << "\n";
      }
    }
  }

 private:
  clang::MangleContext* ctx_;

  std::stack<CalleesSet* > scopes_;
  Callgraph callgraph_;
};

205

206 207 208 209
class FunctionDeclarationFinder
    : public clang::ASTConsumer,
      public clang::RecursiveASTVisitor<FunctionDeclarationFinder> {
 public:
210
  explicit FunctionDeclarationFinder(clang::DiagnosticsEngine& d,
211 212
                                     clang::SourceManager& sm,
                                     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 218 219 220 221 222 223 224 225 226 227 228 229
    callees_printer_ = new CalleesPrinter(mangle_context_);

    TraverseDecl(ctx.getTranslationUnitDecl());

    callees_printer_->PrintCallGraph();
  }

  virtual bool VisitFunctionDecl(clang::FunctionDecl* decl) {
    callees_printer_->AnalyzeFunction(decl);
    return true;
  }

 private:
230
  clang::DiagnosticsEngine& d_;
231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268
  clang::SourceManager& sm_;
  clang::MangleContext* mangle_context_;

  CalleesPrinter* callees_printer_;
};


static bool loaded = false;
static CalleesSet gc_suspects;


static void LoadGCSuspects() {
  if (loaded) return;

  std::ifstream fin("gcsuspects");
  std::string s;

  while (fin >> s) gc_suspects.insert(s);

  loaded = true;
}


static bool KnownToCauseGC(clang::MangleContext* ctx,
                           const clang::FunctionDecl* decl) {
  LoadGCSuspects();

  if (!InV8Namespace(decl)) return false;

  MangledName name;
  if (GetMangledName(ctx, decl, &name)) {
    return gc_suspects.find(name) != gc_suspects.end();
  }

  return false;
}


269 270 271 272 273
static const int kNoEffect = 0;
static const int kCausesGC = 1;
static const int kRawDef = 2;
static const int kRawUse = 4;
static const int kAllEffects = kCausesGC | kRawDef | kRawUse;
274

275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301
class Environment;

class ExprEffect {
 public:
  bool hasGC() { return (effect_ & kCausesGC) != 0; }
  void setGC() { effect_ |= kCausesGC; }

  bool hasRawDef() { return (effect_ & kRawDef) != 0; }
  void setRawDef() { effect_ |= kRawDef; }

  bool hasRawUse() { return (effect_ & kRawUse) != 0; }
  void setRawUse() { effect_ |= kRawUse; }

  static ExprEffect None() { return ExprEffect(kNoEffect, NULL); }
  static ExprEffect NoneWithEnv(Environment* env) {
    return ExprEffect(kNoEffect, env);
  }
  static ExprEffect RawUse() { return ExprEffect(kRawUse, NULL); }

  static ExprEffect Merge(ExprEffect a, ExprEffect b);
  static ExprEffect MergeSeq(ExprEffect a, ExprEffect b);
  ExprEffect Define(const std::string& name);

  Environment* env() {
    return reinterpret_cast<Environment*>(effect_ & ~kAllEffects);
  }

302 303 304 305
  static ExprEffect GC() {
    return ExprEffect(kCausesGC, NULL);
  }

306 307 308 309 310 311 312 313 314 315 316 317 318 319 320
 private:
  ExprEffect(int effect, Environment* env)
      : effect_((effect & kAllEffects) |
                reinterpret_cast<intptr_t>(env)) { }

  intptr_t effect_;
};


const std::string BAD_EXPR_MSG("Possible problem with evaluation order.");
const std::string DEAD_VAR_MSG("Possibly dead variable.");


class Environment {
 public:
321
  Environment() = default;
322 323 324

  static Environment Unreachable() {
    Environment env;
325
    env.unreachable_ = true;
326 327 328 329 330
    return env;
  }

  static Environment Merge(const Environment& l,
                           const Environment& r) {
331 332 333
    Environment out(l);
    out &= r;
    return out;
334 335 336 337
  }

  Environment ApplyEffect(ExprEffect effect) const {
    Environment out = effect.hasGC() ? Environment() : Environment(*this);
338
    if (effect.env()) out |= *effect.env();
339 340 341 342 343 344 345 346
    return out;
  }

  typedef std::map<std::string, int> SymbolTable;

  bool IsAlive(const std::string& name) const {
    SymbolTable::iterator code = symbol_table_.find(name);
    if (code == symbol_table_.end()) return false;
347
    return is_live(code->second);
348 349 350
  }

  bool Equal(const Environment& env) {
351
    if (unreachable_ && env.unreachable_) return true;
352 353 354 355 356
    size_t size = std::max(live_.size(), env.live_.size());
    for (size_t i = 0; i < size; ++i) {
      if (is_live(i) != env.is_live(i)) return false;
    }
    return true;
357 358 359 360 361 362
  }

  Environment Define(const std::string& name) const {
    return Environment(*this, SymbolToCode(name));
  }

363
  void MDefine(const std::string& name) { set_live(SymbolToCode(name)); }
364 365 366 367 368 369 370 371

  static int SymbolToCode(const std::string& name) {
    SymbolTable::iterator code = symbol_table_.find(name);

    if (code == symbol_table_.end()) {
      int new_code = symbol_table_.size();
      symbol_table_.insert(std::make_pair(name, new_code));
      return new_code;
372
    }
373 374 375 376 377

    return code->second;
  }

  static void ClearSymbolTable() {
378
    for (Environment* e : envs_) delete e;
379 380 381 382 383 384 385
    envs_.clear();
    symbol_table_.clear();
  }

  void Print() const {
    bool comma = false;
    std::cout << "{";
386 387 388 389 390
    for (auto& e : symbol_table_) {
      if (!is_live(e.second)) continue;
      if (comma) std::cout << ", ";
      std::cout << e.first;
      comma = true;
391
    }
392
    std::cout << "}";
393 394
  }

395 396 397 398 399 400 401 402 403
  static Environment* Allocate(const Environment& env) {
    Environment* allocated_env = new Environment(env);
    envs_.push_back(allocated_env);
    return allocated_env;
  }

 private:
  Environment(const Environment& l, int code)
      : live_(l.live_) {
404 405 406 407
    set_live(code);
  }

  void set_live(size_t pos) {
408 409
    if (unreachable_) return;
    if (pos >= live_.size()) live_.resize(pos + 1);
410 411 412 413 414 415 416 417
    live_[pos] = true;
  }

  bool is_live(size_t pos) const {
    return unreachable_ || (live_.size() > pos && live_[pos]);
  }

  Environment& operator|=(const Environment& o) {
418 419 420 421 422 423 424
    if (o.unreachable_) {
      unreachable_ = true;
      live_.clear();
    } else if (!unreachable_) {
      for (size_t i = 0, e = o.live_.size(); i < e; ++i) {
        if (o.live_[i]) set_live(i);
      }
425 426 427 428 429
    }
    return *this;
  }

  Environment& operator&=(const Environment& o) {
430 431 432 433 434 435 436
    if (o.unreachable_) return *this;
    if (unreachable_) return *this = o;

    // Carry over false bits from the tail of o.live_, and reset all bits that
    // are not set in o.live_.
    size_t size = std::max(live_.size(), o.live_.size());
    if (size > live_.size()) live_.resize(size);
437
    for (size_t i = 0; i < size; ++i) {
438
      if (live_[i] && (i >= o.live_.size() || !o.live_[i])) live_[i] = false;
439 440
    }
    return *this;
441 442 443
  }

  static SymbolTable symbol_table_;
444
  static std::vector<Environment*> envs_;
445

446
  std::vector<bool> live_;
447 448
  // unreachable_ == true implies live_.empty(), but still is_live(i) returns
  // true for all i.
449
  bool unreachable_ = false;
450 451 452 453 454 455 456 457 458 459 460 461 462 463 464

  friend class ExprEffect;
  friend class CallProps;
};


class CallProps {
 public:
  CallProps() : env_(NULL) { }

  void SetEffect(int arg, ExprEffect in) {
    if (in.hasGC()) gc_.set(arg);
    if (in.hasRawDef()) raw_def_.set(arg);
    if (in.hasRawUse()) raw_use_.set(arg);
    if (in.env() != NULL) {
465 466 467 468 469
      if (env_ == NULL) {
        env_ = in.env();
      } else {
        *env_ |= *in.env();
      }
470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497
    }
  }

  ExprEffect ComputeCumulativeEffect(bool result_is_raw) {
    ExprEffect out = ExprEffect::NoneWithEnv(env_);
    if (gc_.any()) out.setGC();
    if (raw_use_.any()) out.setRawUse();
    if (result_is_raw) out.setRawDef();
    return out;
  }

  bool IsSafe() {
    if (!gc_.any()) return true;
    std::bitset<kMaxNumberOfArguments> raw = (raw_def_ | raw_use_);
    if (!raw.any()) return true;
    return gc_.count() == 1 && !((raw ^ gc_).any());
  }

 private:
  static const int kMaxNumberOfArguments = 64;
  std::bitset<kMaxNumberOfArguments> raw_def_;
  std::bitset<kMaxNumberOfArguments> raw_use_;
  std::bitset<kMaxNumberOfArguments> gc_;
  Environment* env_;
};


Environment::SymbolTable Environment::symbol_table_;
498
std::vector<Environment*> Environment::envs_;
499 500 501 502 503 504 505

ExprEffect ExprEffect::Merge(ExprEffect a, ExprEffect b) {
  Environment* a_env = a.env();
  Environment* b_env = b.env();
  Environment* out = NULL;
  if (a_env != NULL && b_env != NULL) {
    out = Environment::Allocate(*a_env);
506
    *out &= *b_env;
507 508 509 510 511 512 513 514 515 516 517
  }
  return ExprEffect(a.effect_ | b.effect_, out);
}


ExprEffect ExprEffect::MergeSeq(ExprEffect a, ExprEffect b) {
  Environment* a_env = b.hasGC() ? NULL : a.env();
  Environment* b_env = b.env();
  Environment* out = (b_env == NULL) ? a_env : b_env;
  if (a_env != NULL && b_env != NULL) {
    out = Environment::Allocate(*b_env);
518
    *out |= *a_env;
519 520
  }
  return ExprEffect(a.effect_ | b.effect_, out);
521 522 523
}


524 525 526 527 528 529 530 531 532 533 534 535 536 537
ExprEffect ExprEffect::Define(const std::string& name) {
  Environment* e = env();
  if (e == NULL) {
    e = Environment::Allocate(Environment());
  }
  e->MDefine(name);
  return ExprEffect(effect_, e);
}


static std::string THIS ("this");


class FunctionAnalyzer {
538
 public:
539 540 541
  FunctionAnalyzer(clang::MangleContext* ctx,
                   clang::DeclarationName handle_decl_name,
                   clang::CXXRecordDecl* object_decl,
542 543
                   clang::CXXRecordDecl* smi_decl, clang::DiagnosticsEngine& d,
                   clang::SourceManager& sm, bool dead_vars_analysis)
544 545 546 547 548 549 550
      : ctx_(ctx),
        handle_decl_name_(handle_decl_name),
        object_decl_(object_decl),
        smi_decl_(smi_decl),
        d_(d),
        sm_(sm),
        block_(NULL),
551
        dead_vars_analysis_(dead_vars_analysis) {}
552

553 554 555 556 557 558

  // --------------------------------------------------------------------------
  // Expressions
  // --------------------------------------------------------------------------

  ExprEffect VisitExpr(clang::Expr* expr, const Environment& env) {
559 560 561 562 563 564 565
#define VISIT(type)                                                         \
  do {                                                                      \
    clang::type* concrete_expr = llvm::dyn_cast_or_null<clang::type>(expr); \
    if (concrete_expr != NULL) {                                            \
      return Visit##type(concrete_expr, env);                               \
    }                                                                       \
  } while (0);
566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616

    VISIT(AbstractConditionalOperator);
    VISIT(AddrLabelExpr);
    VISIT(ArraySubscriptExpr);
    VISIT(BinaryOperator);
    VISIT(BlockExpr);
    VISIT(CallExpr);
    VISIT(CastExpr);
    VISIT(CharacterLiteral);
    VISIT(ChooseExpr);
    VISIT(CompoundLiteralExpr);
    VISIT(CXXBindTemporaryExpr);
    VISIT(CXXBoolLiteralExpr);
    VISIT(CXXConstructExpr);
    VISIT(CXXDefaultArgExpr);
    VISIT(CXXDeleteExpr);
    VISIT(CXXDependentScopeMemberExpr);
    VISIT(CXXNewExpr);
    VISIT(CXXNoexceptExpr);
    VISIT(CXXNullPtrLiteralExpr);
    VISIT(CXXPseudoDestructorExpr);
    VISIT(CXXScalarValueInitExpr);
    VISIT(CXXThisExpr);
    VISIT(CXXThrowExpr);
    VISIT(CXXTypeidExpr);
    VISIT(CXXUnresolvedConstructExpr);
    VISIT(CXXUuidofExpr);
    VISIT(DeclRefExpr);
    VISIT(DependentScopeDeclRefExpr);
    VISIT(DesignatedInitExpr);
    VISIT(ExprWithCleanups);
    VISIT(ExtVectorElementExpr);
    VISIT(FloatingLiteral);
    VISIT(GNUNullExpr);
    VISIT(ImaginaryLiteral);
    VISIT(ImplicitValueInitExpr);
    VISIT(InitListExpr);
    VISIT(IntegerLiteral);
    VISIT(MemberExpr);
    VISIT(OffsetOfExpr);
    VISIT(OpaqueValueExpr);
    VISIT(OverloadExpr);
    VISIT(PackExpansionExpr);
    VISIT(ParenExpr);
    VISIT(ParenListExpr);
    VISIT(PredefinedExpr);
    VISIT(ShuffleVectorExpr);
    VISIT(SizeOfPackExpr);
    VISIT(StmtExpr);
    VISIT(StringLiteral);
    VISIT(SubstNonTypeTemplateParmPackExpr);
617
    VISIT(TypeTraitExpr);
618 619 620 621 622
    VISIT(UnaryOperator);
    VISIT(VAArgExpr);
#undef VISIT

    return ExprEffect::None();
623 624
  }

625 626
#define DECL_VISIT_EXPR(type)                                           \
  ExprEffect Visit##type (clang::type* expr, const Environment& env)
627

628 629 630 631
#define IGNORE_EXPR(type)                                               \
  ExprEffect Visit##type (clang::type* expr, const Environment& env) {  \
    return ExprEffect::None();                                          \
  }
632

633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653 654 655 656 657 658 659 660 661
  IGNORE_EXPR(AddrLabelExpr);
  IGNORE_EXPR(BlockExpr);
  IGNORE_EXPR(CharacterLiteral);
  IGNORE_EXPR(ChooseExpr);
  IGNORE_EXPR(CompoundLiteralExpr);
  IGNORE_EXPR(CXXBoolLiteralExpr);
  IGNORE_EXPR(CXXDependentScopeMemberExpr);
  IGNORE_EXPR(CXXNullPtrLiteralExpr);
  IGNORE_EXPR(CXXPseudoDestructorExpr);
  IGNORE_EXPR(CXXScalarValueInitExpr);
  IGNORE_EXPR(CXXNoexceptExpr);
  IGNORE_EXPR(CXXTypeidExpr);
  IGNORE_EXPR(CXXUnresolvedConstructExpr);
  IGNORE_EXPR(CXXUuidofExpr);
  IGNORE_EXPR(DependentScopeDeclRefExpr);
  IGNORE_EXPR(DesignatedInitExpr);
  IGNORE_EXPR(ExtVectorElementExpr);
  IGNORE_EXPR(FloatingLiteral);
  IGNORE_EXPR(ImaginaryLiteral);
  IGNORE_EXPR(IntegerLiteral);
  IGNORE_EXPR(OffsetOfExpr);
  IGNORE_EXPR(ImplicitValueInitExpr);
  IGNORE_EXPR(PackExpansionExpr);
  IGNORE_EXPR(PredefinedExpr);
  IGNORE_EXPR(ShuffleVectorExpr);
  IGNORE_EXPR(SizeOfPackExpr);
  IGNORE_EXPR(StmtExpr);
  IGNORE_EXPR(StringLiteral);
  IGNORE_EXPR(SubstNonTypeTemplateParmPackExpr);
662
  IGNORE_EXPR(TypeTraitExpr);
663 664 665 666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682
  IGNORE_EXPR(VAArgExpr);
  IGNORE_EXPR(GNUNullExpr);
  IGNORE_EXPR(OverloadExpr);

  DECL_VISIT_EXPR(CXXThisExpr) {
    return Use(expr, expr->getType(), THIS, env);
  }

  DECL_VISIT_EXPR(AbstractConditionalOperator) {
    Environment after_cond = env.ApplyEffect(VisitExpr(expr->getCond(), env));
    return ExprEffect::Merge(VisitExpr(expr->getTrueExpr(), after_cond),
                             VisitExpr(expr->getFalseExpr(), after_cond));
  }

  DECL_VISIT_EXPR(ArraySubscriptExpr) {
    clang::Expr* exprs[2] = {expr->getBase(), expr->getIdx()};
    return Par(expr, 2, exprs, env);
  }

  bool IsRawPointerVar(clang::Expr* expr, std::string* var_name) {
683 684 685
    if (llvm::isa<clang::DeclRefExpr>(expr)) {
      *var_name =
          llvm::cast<clang::DeclRefExpr>(expr)->getDecl()->getNameAsString();
686
      return true;
687 688 689 690
    }
    return false;
  }

691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713 714
  DECL_VISIT_EXPR(BinaryOperator) {
    clang::Expr* lhs = expr->getLHS();
    clang::Expr* rhs = expr->getRHS();
    clang::Expr* exprs[2] = {lhs, rhs};

    switch (expr->getOpcode()) {
      case clang::BO_Comma:
        return Seq(expr, 2, exprs, env);

      case clang::BO_LAnd:
      case clang::BO_LOr:
        return ExprEffect::Merge(VisitExpr(lhs, env), VisitExpr(rhs, env));

      case clang::BO_Assign: {
        std::string var_name;
        if (IsRawPointerVar(lhs, &var_name)) {
          return VisitExpr(rhs, env).Define(var_name);
        }
        return Par(expr, 2, exprs, env);
      }

      default:
        return Par(expr, 2, exprs, env);
    }
715 716
  }

717 718
  DECL_VISIT_EXPR(CXXBindTemporaryExpr) {
    return VisitExpr(expr->getSubExpr(), env);
719 720
  }

721 722 723 724 725 726 727 728 729 730 731 732
  DECL_VISIT_EXPR(CXXConstructExpr) {
    return VisitArguments<>(expr, env);
  }

  DECL_VISIT_EXPR(CXXDefaultArgExpr) {
    return VisitExpr(expr->getExpr(), env);
  }

  DECL_VISIT_EXPR(CXXDeleteExpr) {
    return VisitExpr(expr->getArgument(), env);
  }

733
  DECL_VISIT_EXPR(CXXNewExpr) { return VisitExpr(expr->getInitializer(), env); }
734 735 736 737 738 739 740 741 742 743 744 745 746 747 748 749 750 751 752 753 754 755 756 757 758 759 760 761 762 763 764 765 766 767 768 769 770 771 772 773 774 775 776 777 778 779 780 781 782 783 784 785 786 787 788 789 790 791 792 793 794 795 796 797 798 799 800 801 802 803 804 805 806 807 808 809 810 811 812 813 814 815 816 817 818 819 820 821

  DECL_VISIT_EXPR(ExprWithCleanups) {
    return VisitExpr(expr->getSubExpr(), env);
  }

  DECL_VISIT_EXPR(CXXThrowExpr) {
    return VisitExpr(expr->getSubExpr(), env);
  }

  DECL_VISIT_EXPR(InitListExpr) {
    return Seq(expr, expr->getNumInits(), expr->getInits(), env);
  }

  DECL_VISIT_EXPR(MemberExpr) {
    return VisitExpr(expr->getBase(), env);
  }

  DECL_VISIT_EXPR(OpaqueValueExpr) {
    return VisitExpr(expr->getSourceExpr(), env);
  }

  DECL_VISIT_EXPR(ParenExpr) {
    return VisitExpr(expr->getSubExpr(), env);
  }

  DECL_VISIT_EXPR(ParenListExpr) {
    return Par(expr, expr->getNumExprs(), expr->getExprs(), env);
  }

  DECL_VISIT_EXPR(UnaryOperator) {
    // TODO We are treating all expressions that look like &raw_pointer_var
    //      as definitions of raw_pointer_var. This should be changed to
    //      recognize less generic pattern:
    //
    //         if (maybe_object->ToObject(&obj)) return maybe_object;
    //
    if (expr->getOpcode() == clang::UO_AddrOf) {
      std::string var_name;
      if (IsRawPointerVar(expr->getSubExpr(), &var_name)) {
        return ExprEffect::None().Define(var_name);
      }
    }
    return VisitExpr(expr->getSubExpr(), env);
  }

  DECL_VISIT_EXPR(CastExpr) {
    return VisitExpr(expr->getSubExpr(), env);
  }

  DECL_VISIT_EXPR(DeclRefExpr) {
    return Use(expr, expr->getDecl(), env);
  }

  ExprEffect Par(clang::Expr* parent,
                 int n,
                 clang::Expr** exprs,
                 const Environment& env) {
    CallProps props;

    for (int i = 0; i < n; ++i) {
      props.SetEffect(i, VisitExpr(exprs[i], env));
    }

    if (!props.IsSafe()) ReportUnsafe(parent, BAD_EXPR_MSG);

    return props.ComputeCumulativeEffect(IsRawPointerType(parent->getType()));
  }

  ExprEffect Seq(clang::Stmt* parent,
                 int n,
                 clang::Expr** exprs,
                 const Environment& env) {
    ExprEffect out = ExprEffect::None();
    Environment out_env = env;
    for (int i = 0; i < n; ++i) {
      out = ExprEffect::MergeSeq(out, VisitExpr(exprs[i], out_env));
      out_env = out_env.ApplyEffect(out);
    }
    return out;
  }

  ExprEffect Use(const clang::Expr* parent,
                 const clang::QualType& var_type,
                 const std::string& var_name,
                 const Environment& env) {
    if (IsRawPointerType(var_type)) {
      if (!env.IsAlive(var_name) && dead_vars_analysis_) {
        ReportUnsafe(parent, DEAD_VAR_MSG);
822
      }
823
      return ExprEffect::RawUse();
824
    }
825 826 827 828 829 830
    return ExprEffect::None();
  }

  ExprEffect Use(const clang::Expr* parent,
                 const clang::ValueDecl* var,
                 const Environment& env) {
831 832 833
    if (IsExternalVMState(var)) {
      return ExprEffect::GC();
    }
834 835 836
    return Use(parent, var->getType(), var->getNameAsString(), env);
  }

837

838 839 840 841 842 843 844 845 846 847 848 849
  template<typename ExprType>
  ExprEffect VisitArguments(ExprType* call, const Environment& env) {
    CallProps props;
    VisitArguments<>(call, &props, env);
    if (!props.IsSafe()) ReportUnsafe(call, BAD_EXPR_MSG);
    return props.ComputeCumulativeEffect(IsRawPointerType(call->getType()));
  }

  template<typename ExprType>
  void VisitArguments(ExprType* call,
                      CallProps* props,
                      const Environment& env) {
850
    for (unsigned arg = 0; arg < call->getNumArgs(); arg++) {
851
      props->SetEffect(arg + 1, VisitExpr(call->getArg(arg), env));
852 853 854
    }
  }

855 856 857 858

  ExprEffect VisitCallExpr(clang::CallExpr* call,
                           const Environment& env) {
    CallProps props;
859 860

    clang::CXXMemberCallExpr* memcall =
861
        llvm::dyn_cast_or_null<clang::CXXMemberCallExpr>(call);
862 863 864
    if (memcall != NULL) {
      clang::Expr* receiver = memcall->getImplicitObjectArgument();
      props.SetEffect(0, VisitExpr(receiver, env));
865 866
    }

867 868 869 870 871 872 873 874 875 876 877 878 879 880 881 882 883 884 885 886
    VisitArguments<>(call, &props, env);

    if (!props.IsSafe()) ReportUnsafe(call, BAD_EXPR_MSG);

    ExprEffect out =
        props.ComputeCumulativeEffect(IsRawPointerType(call->getType()));

    clang::FunctionDecl* callee = call->getDirectCallee();
    if ((callee != NULL) && KnownToCauseGC(ctx_, callee)) {
      out.setGC();
    }

    return out;
  }

  // --------------------------------------------------------------------------
  // Statements
  // --------------------------------------------------------------------------

  Environment VisitStmt(clang::Stmt* stmt, const Environment& env) {
887 888 889 890 891 892 893 894 895
#define VISIT(type)                                                         \
  do {                                                                      \
    clang::type* concrete_stmt = llvm::dyn_cast_or_null<clang::type>(stmt); \
    if (concrete_stmt != NULL) {                                            \
      return Visit##type(concrete_stmt, env);                               \
    }                                                                       \
  } while (0);

    if (clang::Expr* expr = llvm::dyn_cast_or_null<clang::Expr>(stmt)) {
896 897 898 899 900 901 902 903 904 905 906 907 908 909 910 911 912 913 914 915 916 917 918 919 920 921 922 923 924 925 926 927 928 929 930 931 932 933 934 935 936 937 938 939 940 941 942 943 944 945 946 947 948 949 950 951 952 953 954 955 956 957 958 959 960 961 962 963 964 965 966 967 968 969 970 971 972 973 974 975 976 977 978 979 980 981 982 983 984 985 986 987 988 989 990 991 992 993 994 995 996 997 998 999 1000 1001 1002 1003 1004
      return env.ApplyEffect(VisitExpr(expr, env));
    }

    VISIT(AsmStmt);
    VISIT(BreakStmt);
    VISIT(CompoundStmt);
    VISIT(ContinueStmt);
    VISIT(CXXCatchStmt);
    VISIT(CXXTryStmt);
    VISIT(DeclStmt);
    VISIT(DoStmt);
    VISIT(ForStmt);
    VISIT(GotoStmt);
    VISIT(IfStmt);
    VISIT(IndirectGotoStmt);
    VISIT(LabelStmt);
    VISIT(NullStmt);
    VISIT(ReturnStmt);
    VISIT(CaseStmt);
    VISIT(DefaultStmt);
    VISIT(SwitchStmt);
    VISIT(WhileStmt);
#undef VISIT

    return env;
  }

#define DECL_VISIT_STMT(type)                                           \
  Environment Visit##type (clang::type* stmt, const Environment& env)

#define IGNORE_STMT(type)                                               \
  Environment Visit##type (clang::type* stmt, const Environment& env) { \
    return env;                                                         \
  }

  IGNORE_STMT(IndirectGotoStmt);
  IGNORE_STMT(NullStmt);
  IGNORE_STMT(AsmStmt);

  // We are ignoring control flow for simplicity.
  IGNORE_STMT(GotoStmt);
  IGNORE_STMT(LabelStmt);

  // We are ignoring try/catch because V8 does not use them.
  IGNORE_STMT(CXXCatchStmt);
  IGNORE_STMT(CXXTryStmt);

  class Block {
   public:
    Block(const Environment& in,
          FunctionAnalyzer* owner)
        : in_(in),
          out_(Environment::Unreachable()),
          changed_(false),
          owner_(owner) {
      parent_ = owner_->EnterBlock(this);
    }

    ~Block() {
      owner_->LeaveBlock(parent_);
    }

    void MergeIn(const Environment& env) {
      Environment old_in = in_;
      in_ = Environment::Merge(in_, env);
      changed_ = !old_in.Equal(in_);
    }

    bool changed() {
      if (changed_) {
        changed_ = false;
        return true;
      }
      return false;
    }

    const Environment& in() {
      return in_;
    }

    const Environment& out() {
      return out_;
    }

    void MergeOut(const Environment& env) {
      out_ = Environment::Merge(out_, env);
    }

    void Seq(clang::Stmt* a, clang::Stmt* b, clang::Stmt* c) {
      Environment a_out = owner_->VisitStmt(a, in());
      Environment b_out = owner_->VisitStmt(b, a_out);
      Environment c_out = owner_->VisitStmt(c, b_out);
      MergeOut(c_out);
    }

    void Seq(clang::Stmt* a, clang::Stmt* b) {
      Environment a_out = owner_->VisitStmt(a, in());
      Environment b_out = owner_->VisitStmt(b, a_out);
      MergeOut(b_out);
    }

    void Loop(clang::Stmt* a, clang::Stmt* b, clang::Stmt* c) {
      Seq(a, b, c);
      MergeIn(out());
    }

    void Loop(clang::Stmt* a, clang::Stmt* b) {
      Seq(a, b);
      MergeIn(out());
1005
    }
1006 1007 1008 1009 1010 1011 1012 1013 1014 1015 1016 1017 1018 1019 1020 1021 1022 1023 1024 1025 1026 1027 1028 1029 1030 1031 1032 1033 1034 1035 1036 1037 1038 1039 1040 1041 1042 1043 1044 1045 1046 1047 1048 1049 1050 1051 1052 1053 1054 1055 1056 1057 1058 1059 1060 1061 1062 1063 1064 1065 1066 1067 1068 1069 1070 1071 1072 1073 1074 1075 1076 1077 1078 1079 1080 1081 1082 1083 1084 1085 1086 1087 1088 1089 1090


   private:
    Environment in_;
    Environment out_;
    bool changed_;
    FunctionAnalyzer* owner_;
    Block* parent_;
  };


  DECL_VISIT_STMT(BreakStmt) {
    block_->MergeOut(env);
    return Environment::Unreachable();
  }

  DECL_VISIT_STMT(ContinueStmt) {
    block_->MergeIn(env);
    return Environment::Unreachable();
  }

  DECL_VISIT_STMT(CompoundStmt) {
    Environment out = env;
    clang::CompoundStmt::body_iterator end = stmt->body_end();
    for (clang::CompoundStmt::body_iterator s = stmt->body_begin();
         s != end;
         ++s) {
      out = VisitStmt(*s, out);
    }
    return out;
  }

  DECL_VISIT_STMT(WhileStmt) {
    Block block (env, this);
    do {
      block.Loop(stmt->getCond(), stmt->getBody());
    } while (block.changed());
    return block.out();
  }

  DECL_VISIT_STMT(DoStmt) {
    Block block (env, this);
    do {
      block.Loop(stmt->getBody(), stmt->getCond());
    } while (block.changed());
    return block.out();
  }

  DECL_VISIT_STMT(ForStmt) {
    Block block (VisitStmt(stmt->getInit(), env), this);
    do {
      block.Loop(stmt->getCond(),
                 stmt->getBody(),
                 stmt->getInc());
    } while (block.changed());
    return block.out();
  }

  DECL_VISIT_STMT(IfStmt) {
    Environment cond_out = VisitStmt(stmt->getCond(), env);
    Environment then_out = VisitStmt(stmt->getThen(), cond_out);
    Environment else_out = VisitStmt(stmt->getElse(), cond_out);
    return Environment::Merge(then_out, else_out);
  }

  DECL_VISIT_STMT(SwitchStmt) {
    Block block (env, this);
    block.Seq(stmt->getCond(), stmt->getBody());
    return block.out();
  }

  DECL_VISIT_STMT(CaseStmt) {
    Environment in = Environment::Merge(env, block_->in());
    Environment after_lhs = VisitStmt(stmt->getLHS(), in);
    return VisitStmt(stmt->getSubStmt(), after_lhs);
  }

  DECL_VISIT_STMT(DefaultStmt) {
    Environment in = Environment::Merge(env, block_->in());
    return VisitStmt(stmt->getSubStmt(), in);
  }

  DECL_VISIT_STMT(ReturnStmt) {
    VisitExpr(stmt->getRetValue(), env);
    return Environment::Unreachable();
1091 1092 1093 1094 1095
  }

  const clang::TagType* ToTagType(const clang::Type* t) {
    if (t == NULL) {
      return NULL;
1096 1097 1098 1099 1100 1101
    } else if (llvm::isa<clang::TagType>(t)) {
      return llvm::cast<clang::TagType>(t);
    } else if (llvm::isa<clang::SubstTemplateTypeParmType>(t)) {
      return ToTagType(llvm::cast<clang::SubstTemplateTypeParmType>(t)
                           ->getReplacementType()
                           .getTypePtr());
1102 1103 1104 1105 1106
    } else {
      return NULL;
    }
  }

1107 1108 1109 1110
  bool IsDerivedFrom(clang::CXXRecordDecl* record,
                     clang::CXXRecordDecl* base) {
    return (record == base) || record->isDerivedFrom(base);
  }
1111

1112
  bool IsRawPointerType(clang::QualType qtype) {
1113
    const clang::PointerType* type =
1114
        llvm::dyn_cast_or_null<clang::PointerType>(qtype.getTypePtrOrNull());
1115 1116 1117 1118 1119 1120 1121
    if (type == NULL) return false;

    const clang::TagType* pointee =
        ToTagType(type->getPointeeType().getTypePtr());
    if (pointee == NULL) return false;

    clang::CXXRecordDecl* record =
1122
        llvm::dyn_cast_or_null<clang::CXXRecordDecl>(pointee->getDecl());
1123 1124
    if (record == NULL) return false;

1125
    if (!InV8Namespace(record)) return false;
1126

1127
    if (!record->hasDefinition()) return false;
1128

1129
    record = record->getDefinition();
1130

1131 1132
    return IsDerivedFrom(record, object_decl_) &&
        !IsDerivedFrom(record, smi_decl_);
1133 1134
  }

1135
  Environment VisitDecl(clang::Decl* decl, const Environment& env) {
1136
    if (clang::VarDecl* var = llvm::dyn_cast<clang::VarDecl>(decl)) {
1137 1138 1139 1140 1141
      Environment out = var->hasInit() ? VisitStmt(var->getInit(), env) : env;

      if (IsRawPointerType(var->getType())) {
        out = out.Define(var->getNameAsString());
      }
1142

1143 1144 1145 1146
      return out;
    }
    // TODO: handle other declarations?
    return env;
1147 1148
  }

1149 1150 1151 1152 1153 1154 1155 1156 1157
  DECL_VISIT_STMT(DeclStmt) {
    Environment out = env;
    clang::DeclStmt::decl_iterator end = stmt->decl_end();
    for (clang::DeclStmt::decl_iterator decl = stmt->decl_begin();
         decl != end;
         ++decl) {
      out = VisitDecl(*decl, out);
    }
    return out;
1158 1159 1160
  }


1161 1162 1163 1164 1165 1166 1167 1168 1169 1170
  void DefineParameters(const clang::FunctionDecl* f,
                        Environment* env) {
    env->MDefine(THIS);
    clang::FunctionDecl::param_const_iterator end = f->param_end();
    for (clang::FunctionDecl::param_const_iterator p = f->param_begin();
         p != end;
         ++p) {
      env->MDefine((*p)->getNameAsString());
    }
  }
1171 1172


1173 1174 1175 1176 1177 1178 1179 1180 1181
  void AnalyzeFunction(const clang::FunctionDecl* f) {
    const clang::FunctionDecl* body = NULL;
    if (f->hasBody(body)) {
      Environment env;
      DefineParameters(body, &env);
      VisitStmt(body->getBody(), env);
      Environment::ClearSymbolTable();
    }
  }
1182

1183 1184 1185 1186 1187
  Block* EnterBlock(Block* block) {
    Block* parent = block_;
    block_ = block;
    return parent;
  }
1188

1189 1190 1191
  void LeaveBlock(Block* block) {
    block_ = block;
  }
1192

1193 1194 1195
 private:
  void ReportUnsafe(const clang::Expr* expr, const std::string& msg) {
    d_.Report(clang::FullSourceLoc(expr->getExprLoc(), sm_),
1196 1197
              d_.getCustomDiagID(clang::DiagnosticsEngine::Warning, "%0"))
        << msg;
1198
  }
1199 1200


1201 1202 1203 1204
  clang::MangleContext* ctx_;
  clang::DeclarationName handle_decl_name_;
  clang::CXXRecordDecl* object_decl_;
  clang::CXXRecordDecl* smi_decl_;
1205

1206
  clang::DiagnosticsEngine& d_;
1207
  clang::SourceManager& sm_;
1208

1209 1210 1211
  Block* block_;
  bool dead_vars_analysis_;
};
1212 1213


1214 1215 1216
class ProblemsFinder : public clang::ASTConsumer,
                       public clang::RecursiveASTVisitor<ProblemsFinder> {
 public:
1217
  ProblemsFinder(clang::DiagnosticsEngine& d, clang::SourceManager& sm,
1218 1219 1220 1221 1222 1223
                 const std::vector<std::string>& args)
      : d_(d), sm_(sm), dead_vars_analysis_(false) {
    for (unsigned i = 0; i < args.size(); ++i) {
      if (args[i] == "--dead-vars") {
        dead_vars_analysis_ = true;
      }
1224
    }
1225
  }
1226 1227 1228 1229

  virtual void HandleTranslationUnit(clang::ASTContext &ctx) {
    Resolver r(ctx);

1230
    clang::CXXRecordDecl* object_decl =
1231 1232 1233
        r.ResolveNamespace("v8").ResolveNamespace("internal").
            Resolve<clang::CXXRecordDecl>("Object");

1234 1235 1236 1237 1238 1239 1240 1241 1242
    clang::CXXRecordDecl* smi_decl =
        r.ResolveNamespace("v8").ResolveNamespace("internal").
            Resolve<clang::CXXRecordDecl>("Smi");

    if (object_decl != NULL) object_decl = object_decl->getDefinition();

    if (smi_decl != NULL) smi_decl = smi_decl->getDefinition();

    if (object_decl != NULL && smi_decl != NULL) {
1243 1244 1245
      function_analyzer_ = new FunctionAnalyzer(
          clang::ItaniumMangleContext::create(ctx, d_), r.ResolveName("Handle"),
          object_decl, smi_decl, d_, sm_, dead_vars_analysis_);
1246 1247
      TraverseDecl(ctx.getTranslationUnitDecl());
    } else {
1248 1249 1250 1251 1252 1253
      if (object_decl == NULL) {
        llvm::errs() << "Failed to resolve v8::internal::Object\n";
      }
      if (smi_decl == NULL) {
        llvm::errs() << "Failed to resolve v8::internal::Smi\n";
      }
1254 1255 1256
    }
  }

1257 1258
  virtual bool VisitFunctionDecl(clang::FunctionDecl* decl) {
    function_analyzer_->AnalyzeFunction(decl);
1259 1260 1261 1262
    return true;
  }

 private:
1263
  clang::DiagnosticsEngine& d_;
1264
  clang::SourceManager& sm_;
1265
  bool dead_vars_analysis_;
1266

1267
  FunctionAnalyzer* function_analyzer_;
1268 1269 1270 1271 1272 1273 1274 1275
};


template<typename ConsumerType>
class Action : public clang::PluginASTAction {
 protected:
  clang::ASTConsumer *CreateASTConsumer(clang::CompilerInstance &CI,
                                        llvm::StringRef InFile) {
1276
    return new ConsumerType(CI.getDiagnostics(), CI.getSourceManager(), args_);
1277 1278 1279 1280
  }

  bool ParseArgs(const clang::CompilerInstance &CI,
                 const std::vector<std::string>& args) {
1281
    args_ = args;
1282 1283 1284
    return true;
  }

1285 1286 1287 1288
  void PrintHelp(llvm::raw_ostream& ros) {
  }
 private:
  std::vector<std::string> args_;
1289 1290 1291 1292 1293
};


}

1294 1295
static clang::FrontendPluginRegistry::Add<Action<ProblemsFinder> >
FindProblems("find-problems", "Find GC-unsafe places.");
1296

1297 1298
static clang::FrontendPluginRegistry::Add<
  Action<FunctionDeclarationFinder> >
1299
DumpCallees("dump-callees", "Dump callees for each function.");