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