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() = default; 322 323 static Environment Unreachable() { 324 Environment env; 325 env.unreachable_ = true; 326 return env; 327 } 328 329 static Environment Merge(const Environment& l, 330 const Environment& r) { 331 Environment out(l); 332 out &= r; 333 return out; 334 } 335 336 Environment ApplyEffect(ExprEffect effect) const { 337 Environment out = effect.hasGC() ? Environment() : Environment(*this); 338 if (effect.env()) out |= *effect.env(); 339 return out; 340 } 341 342 typedef std::map<std::string, int> SymbolTable; 343 344 bool IsAlive(const std::string& name) const { 345 SymbolTable::iterator code = symbol_table_.find(name); 346 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 size_t size = std::max(live_.size(), env.live_.size()); 353 for (size_t i = 0; i < size; ++i) { 354 if (is_live(i) != env.is_live(i)) return false; 355 } 356 return true; 357 } 358 359 Environment Define(const std::string& name) const { 360 return Environment(*this, SymbolToCode(name)); 361 } 362 363 void MDefine(const std::string& name) { set_live(SymbolToCode(name)); } 364 365 static int SymbolToCode(const std::string& name) { 366 SymbolTable::iterator code = symbol_table_.find(name); 367 368 if (code == symbol_table_.end()) { 369 int new_code = symbol_table_.size(); 370 symbol_table_.insert(std::make_pair(name, new_code)); 371 return new_code; 372 } 373 374 return code->second; 375 } 376 377 static void ClearSymbolTable() { 378 for (Environment* e : envs_) delete e; 379 envs_.clear(); 380 symbol_table_.clear(); 381 } 382 383 void Print() const { 384 bool comma = false; 385 std::cout << "{"; 386 for (auto& e : symbol_table_) { 387 if (!is_live(e.second)) continue; 388 if (comma) std::cout << ", "; 389 std::cout << e.first; 390 comma = true; 391 } 392 std::cout << "}"; 393 } 394 395 static Environment* Allocate(const Environment& env) { 396 Environment* allocated_env = new Environment(env); 397 envs_.push_back(allocated_env); 398 return allocated_env; 399 } 400 401 private: 402 Environment(const Environment& l, int code) 403 : live_(l.live_) { 404 set_live(code); 405 } 406 407 void set_live(size_t pos) { 408 if (unreachable_) return; 409 if (pos >= live_.size()) live_.resize(pos + 1); 410 live_[pos] = true; 411 } 412 413 bool is_live(size_t pos) const { 414 return unreachable_ || (live_.size() > pos && live_[pos]); 415 } 416 417 Environment& operator|=(const Environment& o) { 418 if (o.unreachable_) { 419 unreachable_ = true; 420 live_.clear(); 421 } else if (!unreachable_) { 422 for (size_t i = 0, e = o.live_.size(); i < e; ++i) { 423 if (o.live_[i]) set_live(i); 424 } 425 } 426 return *this; 427 } 428 429 Environment& operator&=(const Environment& o) { 430 if (o.unreachable_) return *this; 431 if (unreachable_) return *this = o; 432 433 // Carry over false bits from the tail of o.live_, and reset all bits that 434 // are not set in o.live_. 435 size_t size = std::max(live_.size(), o.live_.size()); 436 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 // unreachable_ == true implies live_.empty(), but still is_live(i) returns 448 // true for all i. 449 bool unreachable_ = false; 450 451 friend class ExprEffect; 452 friend class CallProps; 453 }; 454 455 456 class CallProps { 457 public: 458 CallProps() : env_(NULL) { } 459 460 void SetEffect(int arg, ExprEffect in) { 461 if (in.hasGC()) gc_.set(arg); 462 if (in.hasRawDef()) raw_def_.set(arg); 463 if (in.hasRawUse()) raw_use_.set(arg); 464 if (in.env() != NULL) { 465 if (env_ == NULL) { 466 env_ = in.env(); 467 } else { 468 *env_ |= *in.env(); 469 } 470 } 471 } 472 473 ExprEffect ComputeCumulativeEffect(bool result_is_raw) { 474 ExprEffect out = ExprEffect::NoneWithEnv(env_); 475 if (gc_.any()) out.setGC(); 476 if (raw_use_.any()) out.setRawUse(); 477 if (result_is_raw) out.setRawDef(); 478 return out; 479 } 480 481 bool IsSafe() { 482 if (!gc_.any()) return true; 483 std::bitset<kMaxNumberOfArguments> raw = (raw_def_ | raw_use_); 484 if (!raw.any()) return true; 485 return gc_.count() == 1 && !((raw ^ gc_).any()); 486 } 487 488 private: 489 static const int kMaxNumberOfArguments = 64; 490 std::bitset<kMaxNumberOfArguments> raw_def_; 491 std::bitset<kMaxNumberOfArguments> raw_use_; 492 std::bitset<kMaxNumberOfArguments> gc_; 493 Environment* env_; 494 }; 495 496 497 Environment::SymbolTable Environment::symbol_table_; 498 std::vector<Environment*> Environment::envs_; 499 500 ExprEffect ExprEffect::Merge(ExprEffect a, ExprEffect b) { 501 Environment* a_env = a.env(); 502 Environment* b_env = b.env(); 503 Environment* out = NULL; 504 if (a_env != NULL && b_env != NULL) { 505 out = Environment::Allocate(*a_env); 506 *out &= *b_env; 507 } 508 return ExprEffect(a.effect_ | b.effect_, out); 509 } 510 511 512 ExprEffect ExprEffect::MergeSeq(ExprEffect a, ExprEffect b) { 513 Environment* a_env = b.hasGC() ? NULL : a.env(); 514 Environment* b_env = b.env(); 515 Environment* out = (b_env == NULL) ? a_env : b_env; 516 if (a_env != NULL && b_env != NULL) { 517 out = Environment::Allocate(*b_env); 518 *out |= *a_env; 519 } 520 return ExprEffect(a.effect_ | b.effect_, out); 521 } 522 523 524 ExprEffect ExprEffect::Define(const std::string& name) { 525 Environment* e = env(); 526 if (e == NULL) { 527 e = Environment::Allocate(Environment()); 528 } 529 e->MDefine(name); 530 return ExprEffect(effect_, e); 531 } 532 533 534 static std::string THIS ("this"); 535 536 537 class FunctionAnalyzer { 538 public: 539 FunctionAnalyzer(clang::MangleContext* ctx, 540 clang::DeclarationName handle_decl_name, 541 clang::CXXRecordDecl* object_decl, 542 clang::CXXRecordDecl* smi_decl, clang::DiagnosticsEngine& d, 543 clang::SourceManager& sm, bool dead_vars_analysis) 544 : ctx_(ctx), 545 handle_decl_name_(handle_decl_name), 546 object_decl_(object_decl), 547 smi_decl_(smi_decl), 548 d_(d), 549 sm_(sm), 550 block_(NULL), 551 dead_vars_analysis_(dead_vars_analysis) {} 552 553 554 // -------------------------------------------------------------------------- 555 // Expressions 556 // -------------------------------------------------------------------------- 557 558 ExprEffect VisitExpr(clang::Expr* expr, const Environment& env) { 559 #define VISIT(type) \ 560 do { \ 561 clang::type* concrete_expr = llvm::dyn_cast_or_null<clang::type>(expr); \ 562 if (concrete_expr != NULL) { \ 563 return Visit##type(concrete_expr, env); \ 564 } \ 565 } while (0); 566 567 VISIT(AbstractConditionalOperator); 568 VISIT(AddrLabelExpr); 569 VISIT(ArraySubscriptExpr); 570 VISIT(BinaryOperator); 571 VISIT(BlockExpr); 572 VISIT(CallExpr); 573 VISIT(CastExpr); 574 VISIT(CharacterLiteral); 575 VISIT(ChooseExpr); 576 VISIT(CompoundLiteralExpr); 577 VISIT(CXXBindTemporaryExpr); 578 VISIT(CXXBoolLiteralExpr); 579 VISIT(CXXConstructExpr); 580 VISIT(CXXDefaultArgExpr); 581 VISIT(CXXDeleteExpr); 582 VISIT(CXXDependentScopeMemberExpr); 583 VISIT(CXXNewExpr); 584 VISIT(CXXNoexceptExpr); 585 VISIT(CXXNullPtrLiteralExpr); 586 VISIT(CXXPseudoDestructorExpr); 587 VISIT(CXXScalarValueInitExpr); 588 VISIT(CXXThisExpr); 589 VISIT(CXXThrowExpr); 590 VISIT(CXXTypeidExpr); 591 VISIT(CXXUnresolvedConstructExpr); 592 VISIT(CXXUuidofExpr); 593 VISIT(DeclRefExpr); 594 VISIT(DependentScopeDeclRefExpr); 595 VISIT(DesignatedInitExpr); 596 VISIT(ExprWithCleanups); 597 VISIT(ExtVectorElementExpr); 598 VISIT(FloatingLiteral); 599 VISIT(GNUNullExpr); 600 VISIT(ImaginaryLiteral); 601 VISIT(ImplicitValueInitExpr); 602 VISIT(InitListExpr); 603 VISIT(IntegerLiteral); 604 VISIT(MemberExpr); 605 VISIT(OffsetOfExpr); 606 VISIT(OpaqueValueExpr); 607 VISIT(OverloadExpr); 608 VISIT(PackExpansionExpr); 609 VISIT(ParenExpr); 610 VISIT(ParenListExpr); 611 VISIT(PredefinedExpr); 612 VISIT(ShuffleVectorExpr); 613 VISIT(SizeOfPackExpr); 614 VISIT(StmtExpr); 615 VISIT(StringLiteral); 616 VISIT(SubstNonTypeTemplateParmPackExpr); 617 VISIT(TypeTraitExpr); 618 VISIT(UnaryOperator); 619 VISIT(VAArgExpr); 620 #undef VISIT 621 622 return ExprEffect::None(); 623 } 624 625 #define DECL_VISIT_EXPR(type) \ 626 ExprEffect Visit##type (clang::type* expr, const Environment& env) 627 628 #define IGNORE_EXPR(type) \ 629 ExprEffect Visit##type (clang::type* expr, const Environment& env) { \ 630 return ExprEffect::None(); \ 631 } 632 633 IGNORE_EXPR(AddrLabelExpr); 634 IGNORE_EXPR(BlockExpr); 635 IGNORE_EXPR(CharacterLiteral); 636 IGNORE_EXPR(ChooseExpr); 637 IGNORE_EXPR(CompoundLiteralExpr); 638 IGNORE_EXPR(CXXBoolLiteralExpr); 639 IGNORE_EXPR(CXXDependentScopeMemberExpr); 640 IGNORE_EXPR(CXXNullPtrLiteralExpr); 641 IGNORE_EXPR(CXXPseudoDestructorExpr); 642 IGNORE_EXPR(CXXScalarValueInitExpr); 643 IGNORE_EXPR(CXXNoexceptExpr); 644 IGNORE_EXPR(CXXTypeidExpr); 645 IGNORE_EXPR(CXXUnresolvedConstructExpr); 646 IGNORE_EXPR(CXXUuidofExpr); 647 IGNORE_EXPR(DependentScopeDeclRefExpr); 648 IGNORE_EXPR(DesignatedInitExpr); 649 IGNORE_EXPR(ExtVectorElementExpr); 650 IGNORE_EXPR(FloatingLiteral); 651 IGNORE_EXPR(ImaginaryLiteral); 652 IGNORE_EXPR(IntegerLiteral); 653 IGNORE_EXPR(OffsetOfExpr); 654 IGNORE_EXPR(ImplicitValueInitExpr); 655 IGNORE_EXPR(PackExpansionExpr); 656 IGNORE_EXPR(PredefinedExpr); 657 IGNORE_EXPR(ShuffleVectorExpr); 658 IGNORE_EXPR(SizeOfPackExpr); 659 IGNORE_EXPR(StmtExpr); 660 IGNORE_EXPR(StringLiteral); 661 IGNORE_EXPR(SubstNonTypeTemplateParmPackExpr); 662 IGNORE_EXPR(TypeTraitExpr); 663 IGNORE_EXPR(VAArgExpr); 664 IGNORE_EXPR(GNUNullExpr); 665 IGNORE_EXPR(OverloadExpr); 666 667 DECL_VISIT_EXPR(CXXThisExpr) { 668 return Use(expr, expr->getType(), THIS, env); 669 } 670 671 DECL_VISIT_EXPR(AbstractConditionalOperator) { 672 Environment after_cond = env.ApplyEffect(VisitExpr(expr->getCond(), env)); 673 return ExprEffect::Merge(VisitExpr(expr->getTrueExpr(), after_cond), 674 VisitExpr(expr->getFalseExpr(), after_cond)); 675 } 676 677 DECL_VISIT_EXPR(ArraySubscriptExpr) { 678 clang::Expr* exprs[2] = {expr->getBase(), expr->getIdx()}; 679 return Par(expr, 2, exprs, env); 680 } 681 682 bool IsRawPointerVar(clang::Expr* expr, std::string* var_name) { 683 if (llvm::isa<clang::DeclRefExpr>(expr)) { 684 *var_name = 685 llvm::cast<clang::DeclRefExpr>(expr)->getDecl()->getNameAsString(); 686 return true; 687 } 688 return false; 689 } 690 691 DECL_VISIT_EXPR(BinaryOperator) { 692 clang::Expr* lhs = expr->getLHS(); 693 clang::Expr* rhs = expr->getRHS(); 694 clang::Expr* exprs[2] = {lhs, rhs}; 695 696 switch (expr->getOpcode()) { 697 case clang::BO_Comma: 698 return Seq(expr, 2, exprs, env); 699 700 case clang::BO_LAnd: 701 case clang::BO_LOr: 702 return ExprEffect::Merge(VisitExpr(lhs, env), VisitExpr(rhs, env)); 703 704 case clang::BO_Assign: { 705 std::string var_name; 706 if (IsRawPointerVar(lhs, &var_name)) { 707 return VisitExpr(rhs, env).Define(var_name); 708 } 709 return Par(expr, 2, exprs, env); 710 } 711 712 default: 713 return Par(expr, 2, exprs, env); 714 } 715 } 716 717 DECL_VISIT_EXPR(CXXBindTemporaryExpr) { 718 return VisitExpr(expr->getSubExpr(), env); 719 } 720 721 DECL_VISIT_EXPR(CXXConstructExpr) { 722 return VisitArguments<>(expr, env); 723 } 724 725 DECL_VISIT_EXPR(CXXDefaultArgExpr) { 726 return VisitExpr(expr->getExpr(), env); 727 } 728 729 DECL_VISIT_EXPR(CXXDeleteExpr) { 730 return VisitExpr(expr->getArgument(), env); 731 } 732 733 DECL_VISIT_EXPR(CXXNewExpr) { return VisitExpr(expr->getInitializer(), env); } 734 735 DECL_VISIT_EXPR(ExprWithCleanups) { 736 return VisitExpr(expr->getSubExpr(), env); 737 } 738 739 DECL_VISIT_EXPR(CXXThrowExpr) { 740 return VisitExpr(expr->getSubExpr(), env); 741 } 742 743 DECL_VISIT_EXPR(InitListExpr) { 744 return Seq(expr, expr->getNumInits(), expr->getInits(), env); 745 } 746 747 DECL_VISIT_EXPR(MemberExpr) { 748 return VisitExpr(expr->getBase(), env); 749 } 750 751 DECL_VISIT_EXPR(OpaqueValueExpr) { 752 return VisitExpr(expr->getSourceExpr(), env); 753 } 754 755 DECL_VISIT_EXPR(ParenExpr) { 756 return VisitExpr(expr->getSubExpr(), env); 757 } 758 759 DECL_VISIT_EXPR(ParenListExpr) { 760 return Par(expr, expr->getNumExprs(), expr->getExprs(), env); 761 } 762 763 DECL_VISIT_EXPR(UnaryOperator) { 764 // TODO We are treating all expressions that look like &raw_pointer_var 765 // as definitions of raw_pointer_var. This should be changed to 766 // recognize less generic pattern: 767 // 768 // if (maybe_object->ToObject(&obj)) return maybe_object; 769 // 770 if (expr->getOpcode() == clang::UO_AddrOf) { 771 std::string var_name; 772 if (IsRawPointerVar(expr->getSubExpr(), &var_name)) { 773 return ExprEffect::None().Define(var_name); 774 } 775 } 776 return VisitExpr(expr->getSubExpr(), env); 777 } 778 779 DECL_VISIT_EXPR(CastExpr) { 780 return VisitExpr(expr->getSubExpr(), env); 781 } 782 783 DECL_VISIT_EXPR(DeclRefExpr) { 784 return Use(expr, expr->getDecl(), env); 785 } 786 787 ExprEffect Par(clang::Expr* parent, 788 int n, 789 clang::Expr** exprs, 790 const Environment& env) { 791 CallProps props; 792 793 for (int i = 0; i < n; ++i) { 794 props.SetEffect(i, VisitExpr(exprs[i], env)); 795 } 796 797 if (!props.IsSafe()) ReportUnsafe(parent, BAD_EXPR_MSG); 798 799 return props.ComputeCumulativeEffect(IsRawPointerType(parent->getType())); 800 } 801 802 ExprEffect Seq(clang::Stmt* parent, 803 int n, 804 clang::Expr** exprs, 805 const Environment& env) { 806 ExprEffect out = ExprEffect::None(); 807 Environment out_env = env; 808 for (int i = 0; i < n; ++i) { 809 out = ExprEffect::MergeSeq(out, VisitExpr(exprs[i], out_env)); 810 out_env = out_env.ApplyEffect(out); 811 } 812 return out; 813 } 814 815 ExprEffect Use(const clang::Expr* parent, 816 const clang::QualType& var_type, 817 const std::string& var_name, 818 const Environment& env) { 819 if (IsRawPointerType(var_type)) { 820 if (!env.IsAlive(var_name) && dead_vars_analysis_) { 821 ReportUnsafe(parent, DEAD_VAR_MSG); 822 } 823 return ExprEffect::RawUse(); 824 } 825 return ExprEffect::None(); 826 } 827 828 ExprEffect Use(const clang::Expr* parent, 829 const clang::ValueDecl* var, 830 const Environment& env) { 831 if (IsExternalVMState(var)) { 832 return ExprEffect::GC(); 833 } 834 return Use(parent, var->getType(), var->getNameAsString(), env); 835 } 836 837 838 template<typename ExprType> 839 ExprEffect VisitArguments(ExprType* call, const Environment& env) { 840 CallProps props; 841 VisitArguments<>(call, &props, env); 842 if (!props.IsSafe()) ReportUnsafe(call, BAD_EXPR_MSG); 843 return props.ComputeCumulativeEffect(IsRawPointerType(call->getType())); 844 } 845 846 template<typename ExprType> 847 void VisitArguments(ExprType* call, 848 CallProps* props, 849 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 ExprEffect VisitCallExpr(clang::CallExpr* call, 857 const Environment& env) { 858 CallProps props; 859 860 clang::CXXMemberCallExpr* memcall = 861 llvm::dyn_cast_or_null<clang::CXXMemberCallExpr>(call); 862 if (memcall != NULL) { 863 clang::Expr* receiver = memcall->getImplicitObjectArgument(); 864 props.SetEffect(0, VisitExpr(receiver, env)); 865 } 866 867 VisitArguments<>(call, &props, env); 868 869 if (!props.IsSafe()) ReportUnsafe(call, BAD_EXPR_MSG); 870 871 ExprEffect out = 872 props.ComputeCumulativeEffect(IsRawPointerType(call->getType())); 873 874 clang::FunctionDecl* callee = call->getDirectCallee(); 875 if ((callee != NULL) && KnownToCauseGC(ctx_, callee)) { 876 out.setGC(); 877 } 878 879 return out; 880 } 881 882 // -------------------------------------------------------------------------- 883 // Statements 884 // -------------------------------------------------------------------------- 885 886 Environment VisitStmt(clang::Stmt* stmt, const Environment& env) { 887 #define VISIT(type) \ 888 do { \ 889 clang::type* concrete_stmt = llvm::dyn_cast_or_null<clang::type>(stmt); \ 890 if (concrete_stmt != NULL) { \ 891 return Visit##type(concrete_stmt, env); \ 892 } \ 893 } while (0); 894 895 if (clang::Expr* expr = llvm::dyn_cast_or_null<clang::Expr>(stmt)) { 896 return env.ApplyEffect(VisitExpr(expr, env)); 897 } 898 899 VISIT(AsmStmt); 900 VISIT(BreakStmt); 901 VISIT(CompoundStmt); 902 VISIT(ContinueStmt); 903 VISIT(CXXCatchStmt); 904 VISIT(CXXTryStmt); 905 VISIT(DeclStmt); 906 VISIT(DoStmt); 907 VISIT(ForStmt); 908 VISIT(GotoStmt); 909 VISIT(IfStmt); 910 VISIT(IndirectGotoStmt); 911 VISIT(LabelStmt); 912 VISIT(NullStmt); 913 VISIT(ReturnStmt); 914 VISIT(CaseStmt); 915 VISIT(DefaultStmt); 916 VISIT(SwitchStmt); 917 VISIT(WhileStmt); 918 #undef VISIT 919 920 return env; 921 } 922 923 #define DECL_VISIT_STMT(type) \ 924 Environment Visit##type (clang::type* stmt, const Environment& env) 925 926 #define IGNORE_STMT(type) \ 927 Environment Visit##type (clang::type* stmt, const Environment& env) { \ 928 return env; \ 929 } 930 931 IGNORE_STMT(IndirectGotoStmt); 932 IGNORE_STMT(NullStmt); 933 IGNORE_STMT(AsmStmt); 934 935 // We are ignoring control flow for simplicity. 936 IGNORE_STMT(GotoStmt); 937 IGNORE_STMT(LabelStmt); 938 939 // We are ignoring try/catch because V8 does not use them. 940 IGNORE_STMT(CXXCatchStmt); 941 IGNORE_STMT(CXXTryStmt); 942 943 class Block { 944 public: 945 Block(const Environment& in, 946 FunctionAnalyzer* owner) 947 : in_(in), 948 out_(Environment::Unreachable()), 949 changed_(false), 950 owner_(owner) { 951 parent_ = owner_->EnterBlock(this); 952 } 953 954 ~Block() { 955 owner_->LeaveBlock(parent_); 956 } 957 958 void MergeIn(const Environment& env) { 959 Environment old_in = in_; 960 in_ = Environment::Merge(in_, env); 961 changed_ = !old_in.Equal(in_); 962 } 963 964 bool changed() { 965 if (changed_) { 966 changed_ = false; 967 return true; 968 } 969 return false; 970 } 971 972 const Environment& in() { 973 return in_; 974 } 975 976 const Environment& out() { 977 return out_; 978 } 979 980 void MergeOut(const Environment& env) { 981 out_ = Environment::Merge(out_, env); 982 } 983 984 void Seq(clang::Stmt* a, clang::Stmt* b, clang::Stmt* c) { 985 Environment a_out = owner_->VisitStmt(a, in()); 986 Environment b_out = owner_->VisitStmt(b, a_out); 987 Environment c_out = owner_->VisitStmt(c, b_out); 988 MergeOut(c_out); 989 } 990 991 void Seq(clang::Stmt* a, clang::Stmt* b) { 992 Environment a_out = owner_->VisitStmt(a, in()); 993 Environment b_out = owner_->VisitStmt(b, a_out); 994 MergeOut(b_out); 995 } 996 997 void Loop(clang::Stmt* a, clang::Stmt* b, clang::Stmt* c) { 998 Seq(a, b, c); 999 MergeIn(out()); 1000 } 1001 1002 void Loop(clang::Stmt* a, clang::Stmt* b) { 1003 Seq(a, b); 1004 MergeIn(out()); 1005 } 1006 1007 1008 private: 1009 Environment in_; 1010 Environment out_; 1011 bool changed_; 1012 FunctionAnalyzer* owner_; 1013 Block* parent_; 1014 }; 1015 1016 1017 DECL_VISIT_STMT(BreakStmt) { 1018 block_->MergeOut(env); 1019 return Environment::Unreachable(); 1020 } 1021 1022 DECL_VISIT_STMT(ContinueStmt) { 1023 block_->MergeIn(env); 1024 return Environment::Unreachable(); 1025 } 1026 1027 DECL_VISIT_STMT(CompoundStmt) { 1028 Environment out = env; 1029 clang::CompoundStmt::body_iterator end = stmt->body_end(); 1030 for (clang::CompoundStmt::body_iterator s = stmt->body_begin(); 1031 s != end; 1032 ++s) { 1033 out = VisitStmt(*s, out); 1034 } 1035 return out; 1036 } 1037 1038 DECL_VISIT_STMT(WhileStmt) { 1039 Block block (env, this); 1040 do { 1041 block.Loop(stmt->getCond(), stmt->getBody()); 1042 } while (block.changed()); 1043 return block.out(); 1044 } 1045 1046 DECL_VISIT_STMT(DoStmt) { 1047 Block block (env, this); 1048 do { 1049 block.Loop(stmt->getBody(), stmt->getCond()); 1050 } while (block.changed()); 1051 return block.out(); 1052 } 1053 1054 DECL_VISIT_STMT(ForStmt) { 1055 Block block (VisitStmt(stmt->getInit(), env), this); 1056 do { 1057 block.Loop(stmt->getCond(), 1058 stmt->getBody(), 1059 stmt->getInc()); 1060 } while (block.changed()); 1061 return block.out(); 1062 } 1063 1064 DECL_VISIT_STMT(IfStmt) { 1065 Environment cond_out = VisitStmt(stmt->getCond(), env); 1066 Environment then_out = VisitStmt(stmt->getThen(), cond_out); 1067 Environment else_out = VisitStmt(stmt->getElse(), cond_out); 1068 return Environment::Merge(then_out, else_out); 1069 } 1070 1071 DECL_VISIT_STMT(SwitchStmt) { 1072 Block block (env, this); 1073 block.Seq(stmt->getCond(), stmt->getBody()); 1074 return block.out(); 1075 } 1076 1077 DECL_VISIT_STMT(CaseStmt) { 1078 Environment in = Environment::Merge(env, block_->in()); 1079 Environment after_lhs = VisitStmt(stmt->getLHS(), in); 1080 return VisitStmt(stmt->getSubStmt(), after_lhs); 1081 } 1082 1083 DECL_VISIT_STMT(DefaultStmt) { 1084 Environment in = Environment::Merge(env, block_->in()); 1085 return VisitStmt(stmt->getSubStmt(), in); 1086 } 1087 1088 DECL_VISIT_STMT(ReturnStmt) { 1089 VisitExpr(stmt->getRetValue(), env); 1090 return Environment::Unreachable(); 1091 } 1092 1093 const clang::TagType* ToTagType(const clang::Type* t) { 1094 if (t == NULL) { 1095 return NULL; 1096 } else if (llvm::isa<clang::TagType>(t)) { 1097 return llvm::cast<clang::TagType>(t); 1098 } else if (llvm::isa<clang::SubstTemplateTypeParmType>(t)) { 1099 return ToTagType(llvm::cast<clang::SubstTemplateTypeParmType>(t) 1100 ->getReplacementType() 1101 .getTypePtr()); 1102 } else { 1103 return NULL; 1104 } 1105 } 1106 1107 bool IsDerivedFrom(clang::CXXRecordDecl* record, 1108 clang::CXXRecordDecl* base) { 1109 return (record == base) || record->isDerivedFrom(base); 1110 } 1111 1112 bool IsRawPointerType(clang::QualType qtype) { 1113 const clang::PointerType* type = 1114 llvm::dyn_cast_or_null<clang::PointerType>(qtype.getTypePtrOrNull()); 1115 if (type == NULL) return false; 1116 1117 const clang::TagType* pointee = 1118 ToTagType(type->getPointeeType().getTypePtr()); 1119 if (pointee == NULL) return false; 1120 1121 clang::CXXRecordDecl* record = 1122 llvm::dyn_cast_or_null<clang::CXXRecordDecl>(pointee->getDecl()); 1123 if (record == NULL) return false; 1124 1125 if (!InV8Namespace(record)) return false; 1126 1127 if (!record->hasDefinition()) return false; 1128 1129 record = record->getDefinition(); 1130 1131 return IsDerivedFrom(record, object_decl_) && 1132 !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 Environment out = var->hasInit() ? VisitStmt(var->getInit(), env) : env; 1138 1139 if (IsRawPointerType(var->getType())) { 1140 out = out.Define(var->getNameAsString()); 1141 } 1142 1143 return out; 1144 } 1145 // TODO: handle other declarations? 1146 return env; 1147 } 1148 1149 DECL_VISIT_STMT(DeclStmt) { 1150 Environment out = env; 1151 clang::DeclStmt::decl_iterator end = stmt->decl_end(); 1152 for (clang::DeclStmt::decl_iterator decl = stmt->decl_begin(); 1153 decl != end; 1154 ++decl) { 1155 out = VisitDecl(*decl, out); 1156 } 1157 return out; 1158 } 1159 1160 1161 void DefineParameters(const clang::FunctionDecl* f, 1162 Environment* env) { 1163 env->MDefine(THIS); 1164 clang::FunctionDecl::param_const_iterator end = f->param_end(); 1165 for (clang::FunctionDecl::param_const_iterator p = f->param_begin(); 1166 p != end; 1167 ++p) { 1168 env->MDefine((*p)->getNameAsString()); 1169 } 1170 } 1171 1172 1173 void AnalyzeFunction(const clang::FunctionDecl* f) { 1174 const clang::FunctionDecl* body = NULL; 1175 if (f->hasBody(body)) { 1176 Environment env; 1177 DefineParameters(body, &env); 1178 VisitStmt(body->getBody(), env); 1179 Environment::ClearSymbolTable(); 1180 } 1181 } 1182 1183 Block* EnterBlock(Block* block) { 1184 Block* parent = block_; 1185 block_ = block; 1186 return parent; 1187 } 1188 1189 void LeaveBlock(Block* block) { 1190 block_ = block; 1191 } 1192 1193 private: 1194 void ReportUnsafe(const clang::Expr* expr, const std::string& msg) { 1195 d_.Report(clang::FullSourceLoc(expr->getExprLoc(), sm_), 1196 d_.getCustomDiagID(clang::DiagnosticsEngine::Warning, "%0")) 1197 << msg; 1198 } 1199 1200 1201 clang::MangleContext* ctx_; 1202 clang::DeclarationName handle_decl_name_; 1203 clang::CXXRecordDecl* object_decl_; 1204 clang::CXXRecordDecl* smi_decl_; 1205 1206 clang::DiagnosticsEngine& d_; 1207 clang::SourceManager& sm_; 1208 1209 Block* block_; 1210 bool dead_vars_analysis_; 1211 }; 1212 1213 1214 class ProblemsFinder : public clang::ASTConsumer, 1215 public clang::RecursiveASTVisitor<ProblemsFinder> { 1216 public: 1217 ProblemsFinder(clang::DiagnosticsEngine& d, clang::SourceManager& sm, 1218 const std::vector<std::string>& args) 1219 : d_(d), sm_(sm), dead_vars_analysis_(false) { 1220 for (unsigned i = 0; i < args.size(); ++i) { 1221 if (args[i] == "--dead-vars") { 1222 dead_vars_analysis_ = true; 1223 } 1224 } 1225 } 1226 1227 virtual void HandleTranslationUnit(clang::ASTContext &ctx) { 1228 Resolver r(ctx); 1229 1230 clang::CXXRecordDecl* object_decl = 1231 r.ResolveNamespace("v8").ResolveNamespace("internal"). 1232 Resolve<clang::CXXRecordDecl>("Object"); 1233 1234 clang::CXXRecordDecl* smi_decl = 1235 r.ResolveNamespace("v8").ResolveNamespace("internal"). 1236 Resolve<clang::CXXRecordDecl>("Smi"); 1237 1238 if (object_decl != NULL) object_decl = object_decl->getDefinition(); 1239 1240 if (smi_decl != NULL) smi_decl = smi_decl->getDefinition(); 1241 1242 if (object_decl != NULL && smi_decl != NULL) { 1243 function_analyzer_ = new FunctionAnalyzer( 1244 clang::ItaniumMangleContext::create(ctx, d_), r.ResolveName("Handle"), 1245 object_decl, smi_decl, d_, sm_, dead_vars_analysis_); 1246 TraverseDecl(ctx.getTranslationUnitDecl()); 1247 } else { 1248 if (object_decl == NULL) { 1249 llvm::errs() << "Failed to resolve v8::internal::Object\n"; 1250 } 1251 if (smi_decl == NULL) { 1252 llvm::errs() << "Failed to resolve v8::internal::Smi\n"; 1253 } 1254 } 1255 } 1256 1257 virtual bool VisitFunctionDecl(clang::FunctionDecl* decl) { 1258 function_analyzer_->AnalyzeFunction(decl); 1259 return true; 1260 } 1261 1262 private: 1263 clang::DiagnosticsEngine& d_; 1264 clang::SourceManager& sm_; 1265 bool dead_vars_analysis_; 1266 1267 FunctionAnalyzer* function_analyzer_; 1268 }; 1269 1270 1271 template<typename ConsumerType> 1272 class Action : public clang::PluginASTAction { 1273 protected: 1274 clang::ASTConsumer *CreateASTConsumer(clang::CompilerInstance &CI, 1275 llvm::StringRef InFile) { 1276 return new ConsumerType(CI.getDiagnostics(), CI.getSourceManager(), args_); 1277 } 1278 1279 bool ParseArgs(const clang::CompilerInstance &CI, 1280 const std::vector<std::string>& args) { 1281 args_ = args; 1282 return true; 1283 } 1284 1285 void PrintHelp(llvm::raw_ostream& ros) { 1286 } 1287 private: 1288 std::vector<std::string> args_; 1289 }; 1290 1291 1292 } 1293 1294 static clang::FrontendPluginRegistry::Add<Action<ProblemsFinder> > 1295 FindProblems("find-problems", "Find GC-unsafe places."); 1296 1297 static clang::FrontendPluginRegistry::Add< 1298 Action<FunctionDeclarationFinder> > 1299 DumpCallees("dump-callees", "Dump callees for each function."); 1300
