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 bool g_tracing_enabled = false;
49 bool g_dead_vars_analysis = false;
50
51 #define TRACE(str) \
52 do { \
53 if (g_tracing_enabled) { \
54 std::cout << str << std::endl; \
55 } \
56 } while (false)
57
58 #define TRACE_LLVM_TYPE(str, type) \
59 do { \
60 if (g_tracing_enabled) { \
61 std::cout << str << " " << type.getAsString() << std::endl; \
62 } \
63 } while (false)
64
65 // Node: The following is used when tracing --dead-vars
66 // to provide extra info for the GC suspect.
67 #define TRACE_LLVM_DECL(str, decl) \
68 do { \
69 if (g_tracing_enabled && g_dead_vars_analysis) { \
70 std::cout << str << std::endl; \
71 decl->dump(); \
72 } \
73 } while (false)
74
75 typedef std::string MangledName;
76 typedef std::set<MangledName> CalleesSet;
77 typedef std::map<MangledName, MangledName> CalleesMap;
78
GetMangledName(clang::MangleContext * ctx,const clang::NamedDecl * decl,MangledName * result)79 static bool GetMangledName(clang::MangleContext* ctx,
80 const clang::NamedDecl* decl,
81 MangledName* result) {
82 if (!llvm::isa<clang::CXXConstructorDecl>(decl) &&
83 !llvm::isa<clang::CXXDestructorDecl>(decl)) {
84 llvm::SmallVector<char, 512> output;
85 llvm::raw_svector_ostream out(output);
86 ctx->mangleName(decl, out);
87 *result = out.str().str();
88 return true;
89 }
90
91 return false;
92 }
93
94
InV8Namespace(const clang::NamedDecl * decl)95 static bool InV8Namespace(const clang::NamedDecl* decl) {
96 return decl->getQualifiedNameAsString().compare(0, 4, "v8::") == 0;
97 }
98
99
100 static std::string EXTERNAL("EXTERNAL");
101 static std::string STATE_TAG("enum v8::internal::StateTag");
102
IsExternalVMState(const clang::ValueDecl * var)103 static bool IsExternalVMState(const clang::ValueDecl* var) {
104 const clang::EnumConstantDecl* enum_constant =
105 llvm::dyn_cast<clang::EnumConstantDecl>(var);
106 if (enum_constant != NULL && enum_constant->getNameAsString() == EXTERNAL) {
107 clang::QualType type = enum_constant->getType();
108 return (type.getAsString() == STATE_TAG);
109 }
110
111 return false;
112 }
113
114
115 struct Resolver {
Resolver__anon79c686130111::Resolver116 explicit Resolver(clang::ASTContext& ctx)
117 : ctx_(ctx), decl_ctx_(ctx.getTranslationUnitDecl()) {
118 }
119
Resolver__anon79c686130111::Resolver120 Resolver(clang::ASTContext& ctx, clang::DeclContext* decl_ctx)
121 : ctx_(ctx), decl_ctx_(decl_ctx) {
122 }
123
ResolveName__anon79c686130111::Resolver124 clang::DeclarationName ResolveName(const char* n) {
125 clang::IdentifierInfo* ident = &ctx_.Idents.get(n);
126 return ctx_.DeclarationNames.getIdentifier(ident);
127 }
128
ResolveNamespace__anon79c686130111::Resolver129 Resolver ResolveNamespace(const char* n) {
130 return Resolver(ctx_, Resolve<clang::NamespaceDecl>(n));
131 }
132
133 template<typename T>
Resolve__anon79c686130111::Resolver134 T* Resolve(const char* n) {
135 if (decl_ctx_ == NULL) return NULL;
136
137 clang::DeclContext::lookup_result result =
138 decl_ctx_->lookup(ResolveName(n));
139
140 clang::DeclContext::lookup_iterator end = result.end();
141 for (clang::DeclContext::lookup_iterator i = result.begin(); i != end;
142 i++) {
143 if (llvm::isa<T>(*i)) {
144 return llvm::cast<T>(*i);
145 } else {
146 llvm::errs() << "Didn't match declaration template against "
147 << (*i)->getNameAsString() << "\n";
148 }
149 }
150
151 return NULL;
152 }
153
ResolveTemplate__anon79c686130111::Resolver154 clang::CXXRecordDecl* ResolveTemplate(const char* n) {
155 clang::NamedDecl* initial_template = Resolve<clang::NamedDecl>(n);
156 if (!initial_template) return NULL;
157
158 clang::NamedDecl* underlying_template =
159 initial_template->getUnderlyingDecl();
160 if (!underlying_template) {
161 llvm::errs() << "Couldn't resolve underlying template\n";
162 return NULL;
163 }
164 const clang::TypeAliasDecl* type_alias_decl =
165 llvm::dyn_cast_or_null<clang::TypeAliasDecl>(underlying_template);
166 if (!type_alias_decl) {
167 llvm::errs() << "Couldn't resolve TypeAliasDecl\n";
168 return NULL;
169 }
170 const clang::Type* type = type_alias_decl->getTypeForDecl();
171 if (!type) {
172 llvm::errs() << "Couldn't resolve TypeAliasDecl to Type\n";
173 return NULL;
174 }
175 const clang::TypedefType* typedef_type =
176 llvm::dyn_cast_or_null<clang::TypedefType>(type);
177 if (!typedef_type) {
178 llvm::errs() << "Couldn't resolve TypedefType\n";
179 return NULL;
180 }
181 const clang::TypedefNameDecl* typedef_name_decl = typedef_type->getDecl();
182 if (!typedef_name_decl) {
183 llvm::errs() << "Couldn't resolve TypedefType to TypedefNameDecl\n";
184 return NULL;
185 }
186
187 clang::QualType underlying_type = typedef_name_decl->getUnderlyingType();
188 if (!llvm::isa<clang::TemplateSpecializationType>(underlying_type)) {
189 llvm::errs() << "Couldn't resolve TemplateSpecializationType\n";
190 return NULL;
191 }
192
193 const clang::TemplateSpecializationType* templ_specialization_type =
194 llvm::cast<clang::TemplateSpecializationType>(underlying_type);
195 if (!llvm::isa<clang::RecordType>(templ_specialization_type->desugar())) {
196 llvm::errs() << "Couldn't resolve RecordType\n";
197 return NULL;
198 }
199
200 const clang::RecordType* record_type =
201 llvm::cast<clang::RecordType>(templ_specialization_type->desugar());
202 clang::CXXRecordDecl* record_decl =
203 llvm::dyn_cast_or_null<clang::CXXRecordDecl>(record_type->getDecl());
204 if (!record_decl) {
205 llvm::errs() << "Couldn't resolve CXXRecordDecl\n";
206 return NULL;
207 }
208 return record_decl;
209 }
210
211 private:
212 clang::ASTContext& ctx_;
213 clang::DeclContext* decl_ctx_;
214 };
215
216
217 class CalleesPrinter : public clang::RecursiveASTVisitor<CalleesPrinter> {
218 public:
CalleesPrinter(clang::MangleContext * ctx)219 explicit CalleesPrinter(clang::MangleContext* ctx) : ctx_(ctx) {
220 }
221
VisitCallExpr(clang::CallExpr * expr)222 virtual bool VisitCallExpr(clang::CallExpr* expr) {
223 const clang::FunctionDecl* callee = expr->getDirectCallee();
224 if (callee != NULL) AnalyzeFunction(callee);
225 return true;
226 }
227
VisitDeclRefExpr(clang::DeclRefExpr * expr)228 virtual bool VisitDeclRefExpr(clang::DeclRefExpr* expr) {
229 // If function mentions EXTERNAL VMState add artificial garbage collection
230 // mark.
231 if (IsExternalVMState(expr->getDecl()))
232 AddCallee("CollectGarbage", "CollectGarbage");
233 return true;
234 }
235
AnalyzeFunction(const clang::FunctionDecl * f)236 void AnalyzeFunction(const clang::FunctionDecl* f) {
237 MangledName name;
238 if (InV8Namespace(f) && GetMangledName(ctx_, f, &name)) {
239 const std::string& function = f->getNameAsString();
240 AddCallee(name, function);
241
242 const clang::FunctionDecl* body = NULL;
243 if (f->hasBody(body) && !Analyzed(name)) {
244 EnterScope(name);
245 TraverseStmt(body->getBody());
246 LeaveScope();
247 }
248 }
249 }
250
251 typedef std::map<MangledName, CalleesSet* > Callgraph;
252
Analyzed(const MangledName & name)253 bool Analyzed(const MangledName& name) {
254 return callgraph_[name] != NULL;
255 }
256
EnterScope(const MangledName & name)257 void EnterScope(const MangledName& name) {
258 CalleesSet* callees = callgraph_[name];
259
260 if (callees == NULL) {
261 callgraph_[name] = callees = new CalleesSet();
262 }
263
264 scopes_.push(callees);
265 }
266
LeaveScope()267 void LeaveScope() {
268 scopes_.pop();
269 }
270
AddCallee(const MangledName & name,const MangledName & function)271 void AddCallee(const MangledName& name, const MangledName& function) {
272 if (!scopes_.empty()) scopes_.top()->insert(name);
273 mangled_to_function_[name] = function;
274 }
275
PrintCallGraph()276 void PrintCallGraph() {
277 for (Callgraph::const_iterator i = callgraph_.begin(), e = callgraph_.end();
278 i != e;
279 ++i) {
280 std::cout << i->first << "," << mangled_to_function_[i->first] << "\n";
281
282 CalleesSet* callees = i->second;
283 for (CalleesSet::const_iterator j = callees->begin(), e = callees->end();
284 j != e;
285 ++j) {
286 std::cout << "\t" << *j << "," << mangled_to_function_[*j] << "\n";
287 }
288 }
289 }
290
291 private:
292 clang::MangleContext* ctx_;
293
294 std::stack<CalleesSet* > scopes_;
295 Callgraph callgraph_;
296 CalleesMap mangled_to_function_;
297 };
298
299
300 class FunctionDeclarationFinder
301 : public clang::ASTConsumer,
302 public clang::RecursiveASTVisitor<FunctionDeclarationFinder> {
303 public:
FunctionDeclarationFinder(clang::DiagnosticsEngine & d,clang::SourceManager & sm,const std::vector<std::string> & args)304 explicit FunctionDeclarationFinder(clang::DiagnosticsEngine& d,
305 clang::SourceManager& sm,
306 const std::vector<std::string>& args)
307 : d_(d), sm_(sm) {}
308
HandleTranslationUnit(clang::ASTContext & ctx)309 virtual void HandleTranslationUnit(clang::ASTContext &ctx) {
310 mangle_context_ = clang::ItaniumMangleContext::create(ctx, d_);
311 callees_printer_ = new CalleesPrinter(mangle_context_);
312
313 TraverseDecl(ctx.getTranslationUnitDecl());
314
315 callees_printer_->PrintCallGraph();
316 }
317
VisitFunctionDecl(clang::FunctionDecl * decl)318 virtual bool VisitFunctionDecl(clang::FunctionDecl* decl) {
319 callees_printer_->AnalyzeFunction(decl);
320 return true;
321 }
322
323 private:
324 clang::DiagnosticsEngine& d_;
325 clang::SourceManager& sm_;
326 clang::MangleContext* mangle_context_;
327
328 CalleesPrinter* callees_printer_;
329 };
330
331 static bool gc_suspects_loaded = false;
332 static CalleesSet gc_suspects;
333 static CalleesSet gc_functions;
334 static bool whitelist_loaded = false;
335 static CalleesSet suspects_whitelist;
336
LoadGCSuspects()337 static void LoadGCSuspects() {
338 if (gc_suspects_loaded) return;
339
340 std::ifstream fin("gcsuspects");
341 std::string mangled, function;
342
343 while (!fin.eof()) {
344 std::getline(fin, mangled, ',');
345 gc_suspects.insert(mangled);
346 std::getline(fin, function);
347 gc_functions.insert(function);
348 }
349
350 gc_suspects_loaded = true;
351 }
352
LoadSuspectsWhitelist()353 static void LoadSuspectsWhitelist() {
354 if (whitelist_loaded) return;
355
356 std::ifstream fin("tools/gcmole/suspects.whitelist");
357 std::string s;
358
359 while (fin >> s) suspects_whitelist.insert(s);
360
361 whitelist_loaded = true;
362 }
363
364 // Looks for exact match of the mangled name.
KnownToCauseGC(clang::MangleContext * ctx,const clang::FunctionDecl * decl)365 static bool KnownToCauseGC(clang::MangleContext* ctx,
366 const clang::FunctionDecl* decl) {
367 LoadGCSuspects();
368
369 if (!InV8Namespace(decl)) return false;
370
371 if (suspects_whitelist.find(decl->getNameAsString()) !=
372 suspects_whitelist.end()) {
373 return false;
374 }
375
376 MangledName name;
377 if (GetMangledName(ctx, decl, &name)) {
378 return gc_suspects.find(name) != gc_suspects.end();
379 }
380
381 return false;
382 }
383
384 // Looks for partial match of only the function name.
SuspectedToCauseGC(clang::MangleContext * ctx,const clang::FunctionDecl * decl)385 static bool SuspectedToCauseGC(clang::MangleContext* ctx,
386 const clang::FunctionDecl* decl) {
387 LoadGCSuspects();
388
389 if (!InV8Namespace(decl)) return false;
390
391 LoadSuspectsWhitelist();
392 if (suspects_whitelist.find(decl->getNameAsString()) !=
393 suspects_whitelist.end()) {
394 return false;
395 }
396
397 if (gc_functions.find(decl->getNameAsString()) != gc_functions.end()) {
398 TRACE_LLVM_DECL("Suspected by ", decl);
399 return true;
400 }
401
402 return false;
403 }
404
405 static const int kNoEffect = 0;
406 static const int kCausesGC = 1;
407 static const int kRawDef = 2;
408 static const int kRawUse = 4;
409 static const int kAllEffects = kCausesGC | kRawDef | kRawUse;
410
411 class Environment;
412
413 class ExprEffect {
414 public:
hasGC()415 bool hasGC() { return (effect_ & kCausesGC) != 0; }
setGC()416 void setGC() { effect_ |= kCausesGC; }
417
hasRawDef()418 bool hasRawDef() { return (effect_ & kRawDef) != 0; }
setRawDef()419 void setRawDef() { effect_ |= kRawDef; }
420
hasRawUse()421 bool hasRawUse() { return (effect_ & kRawUse) != 0; }
setRawUse()422 void setRawUse() { effect_ |= kRawUse; }
423
None()424 static ExprEffect None() { return ExprEffect(kNoEffect, NULL); }
NoneWithEnv(Environment * env)425 static ExprEffect NoneWithEnv(Environment* env) {
426 return ExprEffect(kNoEffect, env);
427 }
RawUse()428 static ExprEffect RawUse() { return ExprEffect(kRawUse, NULL); }
429
430 static ExprEffect Merge(ExprEffect a, ExprEffect b);
431 static ExprEffect MergeSeq(ExprEffect a, ExprEffect b);
432 ExprEffect Define(const std::string& name);
433
env()434 Environment* env() {
435 return reinterpret_cast<Environment*>(effect_ & ~kAllEffects);
436 }
437
GC()438 static ExprEffect GC() {
439 return ExprEffect(kCausesGC, NULL);
440 }
441
442 private:
ExprEffect(int effect,Environment * env)443 ExprEffect(int effect, Environment* env)
444 : effect_((effect & kAllEffects) |
445 reinterpret_cast<intptr_t>(env)) { }
446
447 intptr_t effect_;
448 };
449
450
451 const std::string BAD_EXPR_MSG("Possible problem with evaluation order.");
452 const std::string DEAD_VAR_MSG("Possibly dead variable.");
453
454
455 class Environment {
456 public:
457 Environment() = default;
458
Unreachable()459 static Environment Unreachable() {
460 Environment env;
461 env.unreachable_ = true;
462 return env;
463 }
464
Merge(const Environment & l,const Environment & r)465 static Environment Merge(const Environment& l,
466 const Environment& r) {
467 Environment out(l);
468 out &= r;
469 return out;
470 }
471
ApplyEffect(ExprEffect effect) const472 Environment ApplyEffect(ExprEffect effect) const {
473 Environment out = effect.hasGC() ? Environment() : Environment(*this);
474 if (effect.env()) out |= *effect.env();
475 return out;
476 }
477
478 typedef std::map<std::string, int> SymbolTable;
479
IsAlive(const std::string & name) const480 bool IsAlive(const std::string& name) const {
481 SymbolTable::iterator code = symbol_table_.find(name);
482 if (code == symbol_table_.end()) return false;
483 return is_live(code->second);
484 }
485
Equal(const Environment & env)486 bool Equal(const Environment& env) {
487 if (unreachable_ && env.unreachable_) return true;
488 size_t size = std::max(live_.size(), env.live_.size());
489 for (size_t i = 0; i < size; ++i) {
490 if (is_live(i) != env.is_live(i)) return false;
491 }
492 return true;
493 }
494
Define(const std::string & name) const495 Environment Define(const std::string& name) const {
496 return Environment(*this, SymbolToCode(name));
497 }
498
MDefine(const std::string & name)499 void MDefine(const std::string& name) { set_live(SymbolToCode(name)); }
500
SymbolToCode(const std::string & name)501 static int SymbolToCode(const std::string& name) {
502 SymbolTable::iterator code = symbol_table_.find(name);
503
504 if (code == symbol_table_.end()) {
505 int new_code = symbol_table_.size();
506 symbol_table_.insert(std::make_pair(name, new_code));
507 return new_code;
508 }
509
510 return code->second;
511 }
512
ClearSymbolTable()513 static void ClearSymbolTable() {
514 for (Environment* e : envs_) delete e;
515 envs_.clear();
516 symbol_table_.clear();
517 }
518
Print() const519 void Print() const {
520 bool comma = false;
521 std::cout << "{";
522 for (auto& e : symbol_table_) {
523 if (!is_live(e.second)) continue;
524 if (comma) std::cout << ", ";
525 std::cout << e.first;
526 comma = true;
527 }
528 std::cout << "}" << std::endl;
529 }
530
Allocate(const Environment & env)531 static Environment* Allocate(const Environment& env) {
532 Environment* allocated_env = new Environment(env);
533 envs_.push_back(allocated_env);
534 return allocated_env;
535 }
536
537 private:
Environment(const Environment & l,int code)538 Environment(const Environment& l, int code)
539 : live_(l.live_) {
540 set_live(code);
541 }
542
set_live(size_t pos)543 void set_live(size_t pos) {
544 if (unreachable_) return;
545 if (pos >= live_.size()) live_.resize(pos + 1);
546 live_[pos] = true;
547 }
548
is_live(size_t pos) const549 bool is_live(size_t pos) const {
550 return unreachable_ || (live_.size() > pos && live_[pos]);
551 }
552
operator |=(const Environment & o)553 Environment& operator|=(const Environment& o) {
554 if (o.unreachable_) {
555 unreachable_ = true;
556 live_.clear();
557 } else if (!unreachable_) {
558 for (size_t i = 0, e = o.live_.size(); i < e; ++i) {
559 if (o.live_[i]) set_live(i);
560 }
561 }
562 return *this;
563 }
564
operator &=(const Environment & o)565 Environment& operator&=(const Environment& o) {
566 if (o.unreachable_) return *this;
567 if (unreachable_) return *this = o;
568
569 // Carry over false bits from the tail of o.live_, and reset all bits that
570 // are not set in o.live_.
571 size_t size = std::max(live_.size(), o.live_.size());
572 if (size > live_.size()) live_.resize(size);
573 for (size_t i = 0; i < size; ++i) {
574 if (live_[i] && (i >= o.live_.size() || !o.live_[i])) live_[i] = false;
575 }
576 return *this;
577 }
578
579 static SymbolTable symbol_table_;
580 static std::vector<Environment*> envs_;
581
582 std::vector<bool> live_;
583 // unreachable_ == true implies live_.empty(), but still is_live(i) returns
584 // true for all i.
585 bool unreachable_ = false;
586
587 friend class ExprEffect;
588 friend class CallProps;
589 };
590
591
592 class CallProps {
593 public:
CallProps()594 CallProps() : env_(NULL) { }
595
SetEffect(int arg,ExprEffect in)596 void SetEffect(int arg, ExprEffect in) {
597 if (in.hasGC()) {
598 gc_.set(arg);
599 }
600 if (in.hasRawDef()) raw_def_.set(arg);
601 if (in.hasRawUse()) raw_use_.set(arg);
602 if (in.env() != NULL) {
603 if (env_ == NULL) {
604 env_ = in.env();
605 } else {
606 *env_ |= *in.env();
607 }
608 }
609 }
610
ComputeCumulativeEffect(bool result_is_raw)611 ExprEffect ComputeCumulativeEffect(bool result_is_raw) {
612 ExprEffect out = ExprEffect::NoneWithEnv(env_);
613 if (gc_.any()) {
614 out.setGC();
615 }
616 if (raw_use_.any()) out.setRawUse();
617 if (result_is_raw) out.setRawDef();
618 return out;
619 }
620
IsSafe()621 bool IsSafe() {
622 if (!gc_.any()) {
623 return true;
624 }
625 std::bitset<kMaxNumberOfArguments> raw = (raw_def_ | raw_use_);
626 if (!raw.any()) {
627 return true;
628 }
629 bool result = gc_.count() == 1 && !((raw ^ gc_).any());
630 return result;
631 }
632
633 private:
634 static const int kMaxNumberOfArguments = 64;
635 std::bitset<kMaxNumberOfArguments> raw_def_;
636 std::bitset<kMaxNumberOfArguments> raw_use_;
637 std::bitset<kMaxNumberOfArguments> gc_;
638 Environment* env_;
639 };
640
641
642 Environment::SymbolTable Environment::symbol_table_;
643 std::vector<Environment*> Environment::envs_;
644
Merge(ExprEffect a,ExprEffect b)645 ExprEffect ExprEffect::Merge(ExprEffect a, ExprEffect b) {
646 Environment* a_env = a.env();
647 Environment* b_env = b.env();
648 Environment* out = NULL;
649 if (a_env != NULL && b_env != NULL) {
650 out = Environment::Allocate(*a_env);
651 *out &= *b_env;
652 }
653 return ExprEffect(a.effect_ | b.effect_, out);
654 }
655
656
MergeSeq(ExprEffect a,ExprEffect b)657 ExprEffect ExprEffect::MergeSeq(ExprEffect a, ExprEffect b) {
658 Environment* a_env = b.hasGC() ? NULL : a.env();
659 Environment* b_env = b.env();
660 Environment* out = (b_env == NULL) ? a_env : b_env;
661 if (a_env != NULL && b_env != NULL) {
662 out = Environment::Allocate(*b_env);
663 *out |= *a_env;
664 }
665 return ExprEffect(a.effect_ | b.effect_, out);
666 }
667
668
Define(const std::string & name)669 ExprEffect ExprEffect::Define(const std::string& name) {
670 Environment* e = env();
671 if (e == NULL) {
672 e = Environment::Allocate(Environment());
673 }
674 e->MDefine(name);
675 return ExprEffect(effect_, e);
676 }
677
678
679 static std::string THIS ("this");
680
681
682 class FunctionAnalyzer {
683 public:
FunctionAnalyzer(clang::MangleContext * ctx,clang::CXXRecordDecl * object_decl,clang::CXXRecordDecl * maybe_object_decl,clang::CXXRecordDecl * smi_decl,clang::CXXRecordDecl * no_gc_decl,clang::CXXRecordDecl * no_gc_or_safepoint_decl,clang::CXXRecordDecl * no_heap_access_decl,clang::DiagnosticsEngine & d,clang::SourceManager & sm)684 FunctionAnalyzer(clang::MangleContext* ctx, clang::CXXRecordDecl* object_decl,
685 clang::CXXRecordDecl* maybe_object_decl,
686 clang::CXXRecordDecl* smi_decl,
687 clang::CXXRecordDecl* no_gc_decl,
688 clang::CXXRecordDecl* no_gc_or_safepoint_decl,
689 clang::CXXRecordDecl* no_heap_access_decl,
690 clang::DiagnosticsEngine& d, clang::SourceManager& sm)
691 : ctx_(ctx),
692 object_decl_(object_decl),
693 maybe_object_decl_(maybe_object_decl),
694 smi_decl_(smi_decl),
695 no_gc_decl_(no_gc_decl),
696 no_gc_or_safepoint_decl_(no_gc_or_safepoint_decl),
697 no_heap_access_decl_(no_heap_access_decl),
698 d_(d),
699 sm_(sm),
700 block_(NULL) {}
701
702 // --------------------------------------------------------------------------
703 // Expressions
704 // --------------------------------------------------------------------------
705
VisitExpr(clang::Expr * expr,const Environment & env)706 ExprEffect VisitExpr(clang::Expr* expr, const Environment& env) {
707 #define VISIT(type) \
708 do { \
709 clang::type* concrete_expr = llvm::dyn_cast_or_null<clang::type>(expr); \
710 if (concrete_expr != NULL) { \
711 return Visit##type(concrete_expr, env); \
712 } \
713 } while (0);
714
715 VISIT(AbstractConditionalOperator);
716 VISIT(AddrLabelExpr);
717 VISIT(ArraySubscriptExpr);
718 VISIT(BinaryOperator);
719 VISIT(BlockExpr);
720 VISIT(CallExpr);
721 VISIT(CastExpr);
722 VISIT(CharacterLiteral);
723 VISIT(ChooseExpr);
724 VISIT(CompoundLiteralExpr);
725 VISIT(ConstantExpr);
726 VISIT(CXXBindTemporaryExpr);
727 VISIT(CXXBoolLiteralExpr);
728 VISIT(CXXConstructExpr);
729 VISIT(CXXDefaultArgExpr);
730 VISIT(CXXDeleteExpr);
731 VISIT(CXXDependentScopeMemberExpr);
732 VISIT(CXXNewExpr);
733 VISIT(CXXNoexceptExpr);
734 VISIT(CXXNullPtrLiteralExpr);
735 VISIT(CXXPseudoDestructorExpr);
736 VISIT(CXXScalarValueInitExpr);
737 VISIT(CXXThisExpr);
738 VISIT(CXXThrowExpr);
739 VISIT(CXXTypeidExpr);
740 VISIT(CXXUnresolvedConstructExpr);
741 VISIT(CXXUuidofExpr);
742 VISIT(DeclRefExpr);
743 VISIT(DependentScopeDeclRefExpr);
744 VISIT(DesignatedInitExpr);
745 VISIT(ExprWithCleanups);
746 VISIT(ExtVectorElementExpr);
747 VISIT(FloatingLiteral);
748 VISIT(GNUNullExpr);
749 VISIT(ImaginaryLiteral);
750 VISIT(ImplicitCastExpr);
751 VISIT(ImplicitValueInitExpr);
752 VISIT(InitListExpr);
753 VISIT(IntegerLiteral);
754 VISIT(MaterializeTemporaryExpr);
755 VISIT(MemberExpr);
756 VISIT(OffsetOfExpr);
757 VISIT(OpaqueValueExpr);
758 VISIT(OverloadExpr);
759 VISIT(PackExpansionExpr);
760 VISIT(ParenExpr);
761 VISIT(ParenListExpr);
762 VISIT(PredefinedExpr);
763 VISIT(ShuffleVectorExpr);
764 VISIT(SizeOfPackExpr);
765 VISIT(StmtExpr);
766 VISIT(StringLiteral);
767 VISIT(SubstNonTypeTemplateParmPackExpr);
768 VISIT(TypeTraitExpr);
769 VISIT(UnaryOperator);
770 VISIT(UnaryExprOrTypeTraitExpr);
771 VISIT(VAArgExpr);
772 #undef VISIT
773
774 return ExprEffect::None();
775 }
776
777 #define DECL_VISIT_EXPR(type) \
778 ExprEffect Visit##type (clang::type* expr, const Environment& env)
779
780 #define IGNORE_EXPR(type) \
781 ExprEffect Visit##type (clang::type* expr, const Environment& env) { \
782 return ExprEffect::None(); \
783 }
784
785 IGNORE_EXPR(AddrLabelExpr);
786 IGNORE_EXPR(BlockExpr);
787 IGNORE_EXPR(CharacterLiteral);
788 IGNORE_EXPR(ChooseExpr);
789 IGNORE_EXPR(CompoundLiteralExpr);
790 IGNORE_EXPR(CXXBoolLiteralExpr);
791 IGNORE_EXPR(CXXDependentScopeMemberExpr);
792 IGNORE_EXPR(CXXNullPtrLiteralExpr);
793 IGNORE_EXPR(CXXPseudoDestructorExpr);
794 IGNORE_EXPR(CXXScalarValueInitExpr);
795 IGNORE_EXPR(CXXNoexceptExpr);
796 IGNORE_EXPR(CXXTypeidExpr);
797 IGNORE_EXPR(CXXUnresolvedConstructExpr);
798 IGNORE_EXPR(CXXUuidofExpr);
799 IGNORE_EXPR(DependentScopeDeclRefExpr);
800 IGNORE_EXPR(DesignatedInitExpr);
801 IGNORE_EXPR(ExtVectorElementExpr);
802 IGNORE_EXPR(FloatingLiteral);
803 IGNORE_EXPR(ImaginaryLiteral);
804 IGNORE_EXPR(IntegerLiteral);
805 IGNORE_EXPR(OffsetOfExpr);
806 IGNORE_EXPR(ImplicitValueInitExpr);
807 IGNORE_EXPR(PackExpansionExpr);
808 IGNORE_EXPR(PredefinedExpr);
809 IGNORE_EXPR(ShuffleVectorExpr);
810 IGNORE_EXPR(SizeOfPackExpr);
811 IGNORE_EXPR(StmtExpr);
812 IGNORE_EXPR(StringLiteral);
813 IGNORE_EXPR(SubstNonTypeTemplateParmPackExpr);
814 IGNORE_EXPR(TypeTraitExpr);
815 IGNORE_EXPR(VAArgExpr);
816 IGNORE_EXPR(GNUNullExpr);
817 IGNORE_EXPR(OverloadExpr);
818
DECL_VISIT_EXPR(CXXThisExpr)819 DECL_VISIT_EXPR(CXXThisExpr) {
820 return Use(expr, expr->getType(), THIS, env);
821 }
822
DECL_VISIT_EXPR(AbstractConditionalOperator)823 DECL_VISIT_EXPR(AbstractConditionalOperator) {
824 Environment after_cond = env.ApplyEffect(VisitExpr(expr->getCond(), env));
825 return ExprEffect::Merge(VisitExpr(expr->getTrueExpr(), after_cond),
826 VisitExpr(expr->getFalseExpr(), after_cond));
827 }
828
DECL_VISIT_EXPR(ArraySubscriptExpr)829 DECL_VISIT_EXPR(ArraySubscriptExpr) {
830 clang::Expr* exprs[2] = {expr->getBase(), expr->getIdx()};
831 return Parallel(expr, 2, exprs, env);
832 }
833
IsRawPointerVar(clang::Expr * expr,std::string * var_name)834 bool IsRawPointerVar(clang::Expr* expr, std::string* var_name) {
835 if (llvm::isa<clang::DeclRefExpr>(expr)) {
836 *var_name =
837 llvm::cast<clang::DeclRefExpr>(expr)->getDecl()->getNameAsString();
838 return true;
839 }
840
841 return false;
842 }
843
DECL_VISIT_EXPR(BinaryOperator)844 DECL_VISIT_EXPR(BinaryOperator) {
845 clang::Expr* lhs = expr->getLHS();
846 clang::Expr* rhs = expr->getRHS();
847 clang::Expr* exprs[2] = {lhs, rhs};
848
849 switch (expr->getOpcode()) {
850 case clang::BO_Comma:
851 return Sequential(expr, 2, exprs, env);
852
853 case clang::BO_LAnd:
854 case clang::BO_LOr:
855 return ExprEffect::Merge(VisitExpr(lhs, env), VisitExpr(rhs, env));
856
857 default:
858 return Parallel(expr, 2, exprs, env);
859 }
860 }
861
DECL_VISIT_EXPR(CXXBindTemporaryExpr)862 DECL_VISIT_EXPR(CXXBindTemporaryExpr) {
863 return VisitExpr(expr->getSubExpr(), env);
864 }
865
DECL_VISIT_EXPR(MaterializeTemporaryExpr)866 DECL_VISIT_EXPR(MaterializeTemporaryExpr) {
867 return VisitExpr(expr->GetTemporaryExpr(), env);
868 }
869
DECL_VISIT_EXPR(CXXConstructExpr)870 DECL_VISIT_EXPR(CXXConstructExpr) {
871 return VisitArguments<>(expr, env);
872 }
873
DECL_VISIT_EXPR(CXXDefaultArgExpr)874 DECL_VISIT_EXPR(CXXDefaultArgExpr) {
875 return VisitExpr(expr->getExpr(), env);
876 }
877
DECL_VISIT_EXPR(CXXDeleteExpr)878 DECL_VISIT_EXPR(CXXDeleteExpr) {
879 return VisitExpr(expr->getArgument(), env);
880 }
881
DECL_VISIT_EXPR(CXXNewExpr)882 DECL_VISIT_EXPR(CXXNewExpr) { return VisitExpr(expr->getInitializer(), env); }
883
DECL_VISIT_EXPR(ExprWithCleanups)884 DECL_VISIT_EXPR(ExprWithCleanups) {
885 return VisitExpr(expr->getSubExpr(), env);
886 }
887
DECL_VISIT_EXPR(CXXThrowExpr)888 DECL_VISIT_EXPR(CXXThrowExpr) {
889 return VisitExpr(expr->getSubExpr(), env);
890 }
891
DECL_VISIT_EXPR(ImplicitCastExpr)892 DECL_VISIT_EXPR(ImplicitCastExpr) {
893 return VisitExpr(expr->getSubExpr(), env);
894 }
895
DECL_VISIT_EXPR(ConstantExpr)896 DECL_VISIT_EXPR(ConstantExpr) { return VisitExpr(expr->getSubExpr(), env); }
897
DECL_VISIT_EXPR(InitListExpr)898 DECL_VISIT_EXPR(InitListExpr) {
899 return Sequential(expr, expr->getNumInits(), expr->getInits(), env);
900 }
901
DECL_VISIT_EXPR(MemberExpr)902 DECL_VISIT_EXPR(MemberExpr) {
903 return VisitExpr(expr->getBase(), env);
904 }
905
DECL_VISIT_EXPR(OpaqueValueExpr)906 DECL_VISIT_EXPR(OpaqueValueExpr) {
907 return VisitExpr(expr->getSourceExpr(), env);
908 }
909
DECL_VISIT_EXPR(ParenExpr)910 DECL_VISIT_EXPR(ParenExpr) {
911 return VisitExpr(expr->getSubExpr(), env);
912 }
913
DECL_VISIT_EXPR(ParenListExpr)914 DECL_VISIT_EXPR(ParenListExpr) {
915 return Parallel(expr, expr->getNumExprs(), expr->getExprs(), env);
916 }
917
DECL_VISIT_EXPR(UnaryOperator)918 DECL_VISIT_EXPR(UnaryOperator) {
919 // TODO(gcmole): We are treating all expressions that look like
920 // {&raw_pointer_var} as definitions of {raw_pointer_var}. This should be
921 // changed to recognize less generic pattern:
922 //
923 // if (maybe_object->ToObject(&obj)) return maybe_object;
924 //
925 if (expr->getOpcode() == clang::UO_AddrOf) {
926 std::string var_name;
927 if (IsRawPointerVar(expr->getSubExpr(), &var_name)) {
928 return ExprEffect::None().Define(var_name);
929 }
930 }
931 return VisitExpr(expr->getSubExpr(), env);
932 }
933
DECL_VISIT_EXPR(UnaryExprOrTypeTraitExpr)934 DECL_VISIT_EXPR(UnaryExprOrTypeTraitExpr) {
935 if (expr->isArgumentType()) {
936 return ExprEffect::None();
937 }
938
939 return VisitExpr(expr->getArgumentExpr(), env);
940 }
941
DECL_VISIT_EXPR(CastExpr)942 DECL_VISIT_EXPR(CastExpr) {
943 return VisitExpr(expr->getSubExpr(), env);
944 }
945
DECL_VISIT_EXPR(DeclRefExpr)946 DECL_VISIT_EXPR(DeclRefExpr) {
947 return Use(expr, expr->getDecl(), env);
948 }
949
950 // Represents a node in the AST {parent} whose children {exprs} have
951 // undefined order of evaluation, e.g. array subscript or a binary operator.
Parallel(clang::Expr * parent,int n,clang::Expr ** exprs,const Environment & env)952 ExprEffect Parallel(clang::Expr* parent, int n, clang::Expr** exprs,
953 const Environment& env) {
954 CallProps props;
955
956 for (int i = 0; i < n; ++i) {
957 props.SetEffect(i, VisitExpr(exprs[i], env));
958 }
959
960 if (!props.IsSafe()) ReportUnsafe(parent, BAD_EXPR_MSG);
961
962 return props.ComputeCumulativeEffect(
963 RepresentsRawPointerType(parent->getType()));
964 }
965
966 // Represents a node in the AST {parent} whose children {exprs} are
967 // executed in sequence, e.g. a switch statement or an initializer list.
Sequential(clang::Stmt * parent,int n,clang::Expr ** exprs,const Environment & env)968 ExprEffect Sequential(clang::Stmt* parent, int n, clang::Expr** exprs,
969 const Environment& env) {
970 ExprEffect out = ExprEffect::None();
971 Environment out_env = env;
972 for (int i = 0; i < n; ++i) {
973 out = ExprEffect::MergeSeq(out, VisitExpr(exprs[i], out_env));
974 out_env = out_env.ApplyEffect(out);
975 }
976 return out;
977 }
978
979 // Represents a node in the AST {parent} which uses the variable {var_name},
980 // e.g. this expression or operator&.
981 // Here we observe the type in {var_type} of a previously declared variable
982 // and if it's a raw heap object type, we do the following:
983 // 1. If it got stale due to GC since its declaration, we report it as such.
984 // 2. Mark its raw usage in the ExprEffect returned by this function.
Use(const clang::Expr * parent,const clang::QualType & var_type,const std::string & var_name,const Environment & env)985 ExprEffect Use(const clang::Expr* parent,
986 const clang::QualType& var_type,
987 const std::string& var_name,
988 const Environment& env) {
989 if (RepresentsRawPointerType(var_type)) {
990 // We currently care only about our internal pointer types and not about
991 // raw C++ pointers, because normally special care is taken when storing
992 // raw pointers to the managed heap. Furthermore, checking for raw
993 // pointers produces too many false positives in the dead variable
994 // analysis.
995 if (IsInternalPointerType(var_type) && !env.IsAlive(var_name) &&
996 !HasActiveGuard() && g_dead_vars_analysis) {
997 ReportUnsafe(parent, DEAD_VAR_MSG);
998 }
999 return ExprEffect::RawUse();
1000 }
1001 return ExprEffect::None();
1002 }
1003
Use(const clang::Expr * parent,const clang::ValueDecl * var,const Environment & env)1004 ExprEffect Use(const clang::Expr* parent,
1005 const clang::ValueDecl* var,
1006 const Environment& env) {
1007 if (IsExternalVMState(var)) {
1008 return ExprEffect::GC();
1009 }
1010 return Use(parent, var->getType(), var->getNameAsString(), env);
1011 }
1012
1013
1014 template<typename ExprType>
VisitArguments(ExprType * call,const Environment & env)1015 ExprEffect VisitArguments(ExprType* call, const Environment& env) {
1016 CallProps props;
1017 VisitArguments<>(call, &props, env);
1018 if (!props.IsSafe()) ReportUnsafe(call, BAD_EXPR_MSG);
1019 return props.ComputeCumulativeEffect(
1020 RepresentsRawPointerType(call->getType()));
1021 }
1022
1023 template<typename ExprType>
VisitArguments(ExprType * call,CallProps * props,const Environment & env)1024 void VisitArguments(ExprType* call,
1025 CallProps* props,
1026 const Environment& env) {
1027 for (unsigned arg = 0; arg < call->getNumArgs(); arg++) {
1028 props->SetEffect(arg + 1, VisitExpr(call->getArg(arg), env));
1029 }
1030 }
1031
1032 // After visiting the receiver and the arguments of the {call} node, this
1033 // function might report a GC-unsafe usage (due to the undefined evaluation
1034 // order of the receiver and the rest of the arguments).
VisitCallExpr(clang::CallExpr * call,const Environment & env)1035 ExprEffect VisitCallExpr(clang::CallExpr* call,
1036 const Environment& env) {
1037 CallProps props;
1038
1039 clang::CXXMemberCallExpr* memcall =
1040 llvm::dyn_cast_or_null<clang::CXXMemberCallExpr>(call);
1041 if (memcall != NULL) {
1042 clang::Expr* receiver = memcall->getImplicitObjectArgument();
1043 props.SetEffect(0, VisitExpr(receiver, env));
1044 }
1045
1046 std::string var_name;
1047 clang::CXXOperatorCallExpr* opcall =
1048 llvm::dyn_cast_or_null<clang::CXXOperatorCallExpr>(call);
1049 if (opcall != NULL && opcall->isAssignmentOp() &&
1050 IsRawPointerVar(opcall->getArg(0), &var_name)) {
1051 // TODO(gcmole): We are treating all assignment operator calls with
1052 // the left hand side looking like {raw_pointer_var} as safe independent
1053 // of the concrete assignment operator implementation. This should be
1054 // changed to be more narrow only if the assignment operator of the base
1055 // {Object} or {HeapObject} class was used, which we know to be safe.
1056 props.SetEffect(1, VisitExpr(call->getArg(1), env).Define(var_name));
1057 } else {
1058 VisitArguments<>(call, &props, env);
1059 }
1060
1061 if (!props.IsSafe()) ReportUnsafe(call, BAD_EXPR_MSG);
1062
1063 ExprEffect out = props.ComputeCumulativeEffect(
1064 RepresentsRawPointerType(call->getType()));
1065
1066 clang::FunctionDecl* callee = call->getDirectCallee();
1067 if (callee != NULL) {
1068 if (KnownToCauseGC(ctx_, callee)) {
1069 out.setGC();
1070 scopes_.back().SetGCCauseLocation(
1071 clang::FullSourceLoc(call->getExprLoc(), sm_));
1072 }
1073
1074 // Support for virtual methods that might be GC suspects.
1075 clang::CXXMethodDecl* method =
1076 llvm::dyn_cast_or_null<clang::CXXMethodDecl>(callee);
1077 if (method != NULL && method->isVirtual()) {
1078 clang::CXXMemberCallExpr* memcall =
1079 llvm::dyn_cast_or_null<clang::CXXMemberCallExpr>(call);
1080 if (memcall != NULL) {
1081 clang::CXXMethodDecl* target = method->getDevirtualizedMethod(
1082 memcall->getImplicitObjectArgument(), false);
1083 if (target != NULL) {
1084 if (KnownToCauseGC(ctx_, target)) {
1085 out.setGC();
1086 scopes_.back().SetGCCauseLocation(
1087 clang::FullSourceLoc(call->getExprLoc(), sm_));
1088 }
1089 } else {
1090 // According to the documentation, {getDevirtualizedMethod} might
1091 // return NULL, in which case we still want to use the partial
1092 // match of the {method}'s name against the GC suspects in order
1093 // to increase coverage.
1094 if (SuspectedToCauseGC(ctx_, method)) {
1095 out.setGC();
1096 scopes_.back().SetGCCauseLocation(
1097 clang::FullSourceLoc(call->getExprLoc(), sm_));
1098 }
1099 }
1100 }
1101 }
1102 }
1103
1104 return out;
1105 }
1106
1107 // --------------------------------------------------------------------------
1108 // Statements
1109 // --------------------------------------------------------------------------
1110
VisitStmt(clang::Stmt * stmt,const Environment & env)1111 Environment VisitStmt(clang::Stmt* stmt, const Environment& env) {
1112 #define VISIT(type) \
1113 do { \
1114 clang::type* concrete_stmt = llvm::dyn_cast_or_null<clang::type>(stmt); \
1115 if (concrete_stmt != NULL) { \
1116 return Visit##type(concrete_stmt, env); \
1117 } \
1118 } while (0);
1119
1120 if (clang::Expr* expr = llvm::dyn_cast_or_null<clang::Expr>(stmt)) {
1121 return env.ApplyEffect(VisitExpr(expr, env));
1122 }
1123
1124 VISIT(AsmStmt);
1125 VISIT(BreakStmt);
1126 VISIT(CompoundStmt);
1127 VISIT(ContinueStmt);
1128 VISIT(CXXCatchStmt);
1129 VISIT(CXXTryStmt);
1130 VISIT(DeclStmt);
1131 VISIT(DoStmt);
1132 VISIT(ForStmt);
1133 VISIT(GotoStmt);
1134 VISIT(IfStmt);
1135 VISIT(IndirectGotoStmt);
1136 VISIT(LabelStmt);
1137 VISIT(NullStmt);
1138 VISIT(ReturnStmt);
1139 VISIT(CaseStmt);
1140 VISIT(DefaultStmt);
1141 VISIT(SwitchStmt);
1142 VISIT(WhileStmt);
1143 #undef VISIT
1144
1145 return env;
1146 }
1147
1148 #define DECL_VISIT_STMT(type) \
1149 Environment Visit##type (clang::type* stmt, const Environment& env)
1150
1151 #define IGNORE_STMT(type) \
1152 Environment Visit##type (clang::type* stmt, const Environment& env) { \
1153 return env; \
1154 }
1155
1156 IGNORE_STMT(IndirectGotoStmt);
1157 IGNORE_STMT(NullStmt);
1158 IGNORE_STMT(AsmStmt);
1159
1160 // We are ignoring control flow for simplicity.
1161 IGNORE_STMT(GotoStmt);
1162 IGNORE_STMT(LabelStmt);
1163
1164 // We are ignoring try/catch because V8 does not use them.
1165 IGNORE_STMT(CXXCatchStmt);
1166 IGNORE_STMT(CXXTryStmt);
1167
1168 class Block {
1169 public:
Block(const Environment & in,FunctionAnalyzer * owner)1170 Block(const Environment& in,
1171 FunctionAnalyzer* owner)
1172 : in_(in),
1173 out_(Environment::Unreachable()),
1174 changed_(false),
1175 owner_(owner) {
1176 parent_ = owner_->EnterBlock(this);
1177 }
1178
~Block()1179 ~Block() {
1180 owner_->LeaveBlock(parent_);
1181 }
1182
MergeIn(const Environment & env)1183 void MergeIn(const Environment& env) {
1184 Environment old_in = in_;
1185 in_ = Environment::Merge(in_, env);
1186 changed_ = !old_in.Equal(in_);
1187 }
1188
changed()1189 bool changed() {
1190 if (changed_) {
1191 changed_ = false;
1192 return true;
1193 }
1194 return false;
1195 }
1196
in()1197 const Environment& in() {
1198 return in_;
1199 }
1200
out()1201 const Environment& out() {
1202 return out_;
1203 }
1204
MergeOut(const Environment & env)1205 void MergeOut(const Environment& env) {
1206 out_ = Environment::Merge(out_, env);
1207 }
1208
Sequential(clang::Stmt * a,clang::Stmt * b,clang::Stmt * c)1209 void Sequential(clang::Stmt* a, clang::Stmt* b, clang::Stmt* c) {
1210 Environment a_out = owner_->VisitStmt(a, in());
1211 Environment b_out = owner_->VisitStmt(b, a_out);
1212 Environment c_out = owner_->VisitStmt(c, b_out);
1213 MergeOut(c_out);
1214 }
1215
Sequential(clang::Stmt * a,clang::Stmt * b)1216 void Sequential(clang::Stmt* a, clang::Stmt* b) {
1217 Environment a_out = owner_->VisitStmt(a, in());
1218 Environment b_out = owner_->VisitStmt(b, a_out);
1219 MergeOut(b_out);
1220 }
1221
Loop(clang::Stmt * a,clang::Stmt * b,clang::Stmt * c)1222 void Loop(clang::Stmt* a, clang::Stmt* b, clang::Stmt* c) {
1223 Sequential(a, b, c);
1224 MergeIn(out());
1225 }
1226
Loop(clang::Stmt * a,clang::Stmt * b)1227 void Loop(clang::Stmt* a, clang::Stmt* b) {
1228 Sequential(a, b);
1229 MergeIn(out());
1230 }
1231
1232
1233 private:
1234 Environment in_;
1235 Environment out_;
1236 bool changed_;
1237 FunctionAnalyzer* owner_;
1238 Block* parent_;
1239 };
1240
1241
DECL_VISIT_STMT(BreakStmt)1242 DECL_VISIT_STMT(BreakStmt) {
1243 block_->MergeOut(env);
1244 return Environment::Unreachable();
1245 }
1246
DECL_VISIT_STMT(ContinueStmt)1247 DECL_VISIT_STMT(ContinueStmt) {
1248 block_->MergeIn(env);
1249 return Environment::Unreachable();
1250 }
1251
DECL_VISIT_STMT(CompoundStmt)1252 DECL_VISIT_STMT(CompoundStmt) {
1253 scopes_.push_back(GCScope());
1254 Environment out = env;
1255 clang::CompoundStmt::body_iterator end = stmt->body_end();
1256 for (clang::CompoundStmt::body_iterator s = stmt->body_begin();
1257 s != end;
1258 ++s) {
1259 out = VisitStmt(*s, out);
1260 }
1261 scopes_.pop_back();
1262 return out;
1263 }
1264
DECL_VISIT_STMT(WhileStmt)1265 DECL_VISIT_STMT(WhileStmt) {
1266 Block block (env, this);
1267 do {
1268 block.Loop(stmt->getCond(), stmt->getBody());
1269 } while (block.changed());
1270 return block.out();
1271 }
1272
DECL_VISIT_STMT(DoStmt)1273 DECL_VISIT_STMT(DoStmt) {
1274 Block block (env, this);
1275 do {
1276 block.Loop(stmt->getBody(), stmt->getCond());
1277 } while (block.changed());
1278 return block.out();
1279 }
1280
DECL_VISIT_STMT(ForStmt)1281 DECL_VISIT_STMT(ForStmt) {
1282 Block block (VisitStmt(stmt->getInit(), env), this);
1283 do {
1284 block.Loop(stmt->getCond(),
1285 stmt->getBody(),
1286 stmt->getInc());
1287 } while (block.changed());
1288 return block.out();
1289 }
1290
DECL_VISIT_STMT(IfStmt)1291 DECL_VISIT_STMT(IfStmt) {
1292 Environment cond_out = VisitStmt(stmt->getCond(), env);
1293 Environment then_out = VisitStmt(stmt->getThen(), cond_out);
1294 Environment else_out = VisitStmt(stmt->getElse(), cond_out);
1295 return Environment::Merge(then_out, else_out);
1296 }
1297
DECL_VISIT_STMT(SwitchStmt)1298 DECL_VISIT_STMT(SwitchStmt) {
1299 Block block (env, this);
1300 block.Sequential(stmt->getCond(), stmt->getBody());
1301 return block.out();
1302 }
1303
DECL_VISIT_STMT(CaseStmt)1304 DECL_VISIT_STMT(CaseStmt) {
1305 Environment in = Environment::Merge(env, block_->in());
1306 Environment after_lhs = VisitStmt(stmt->getLHS(), in);
1307 return VisitStmt(stmt->getSubStmt(), after_lhs);
1308 }
1309
DECL_VISIT_STMT(DefaultStmt)1310 DECL_VISIT_STMT(DefaultStmt) {
1311 Environment in = Environment::Merge(env, block_->in());
1312 return VisitStmt(stmt->getSubStmt(), in);
1313 }
1314
DECL_VISIT_STMT(ReturnStmt)1315 DECL_VISIT_STMT(ReturnStmt) {
1316 VisitExpr(stmt->getRetValue(), env);
1317 return Environment::Unreachable();
1318 }
1319
ToTagType(const clang::Type * t)1320 const clang::TagType* ToTagType(const clang::Type* t) {
1321 if (t == NULL) {
1322 return NULL;
1323 } else if (llvm::isa<clang::TagType>(t)) {
1324 return llvm::cast<clang::TagType>(t);
1325 } else if (llvm::isa<clang::SubstTemplateTypeParmType>(t)) {
1326 return ToTagType(llvm::cast<clang::SubstTemplateTypeParmType>(t)
1327 ->getReplacementType()
1328 .getTypePtr());
1329 } else {
1330 return NULL;
1331 }
1332 }
1333
IsDerivedFrom(const clang::CXXRecordDecl * record,const clang::CXXRecordDecl * base)1334 bool IsDerivedFrom(const clang::CXXRecordDecl* record,
1335 const clang::CXXRecordDecl* base) {
1336 return (record == base) || record->isDerivedFrom(base);
1337 }
1338
GetDefinitionOrNull(const clang::CXXRecordDecl * record)1339 const clang::CXXRecordDecl* GetDefinitionOrNull(
1340 const clang::CXXRecordDecl* record) {
1341 if (record == NULL) {
1342 return NULL;
1343 }
1344
1345 if (!InV8Namespace(record)) return NULL;
1346
1347 if (!record->hasDefinition()) {
1348 return NULL;
1349 }
1350
1351 return record->getDefinition();
1352 }
1353
IsDerivedFromInternalPointer(const clang::CXXRecordDecl * record)1354 bool IsDerivedFromInternalPointer(const clang::CXXRecordDecl* record) {
1355 const clang::CXXRecordDecl* definition = GetDefinitionOrNull(record);
1356 if (!definition) {
1357 return false;
1358 }
1359
1360 bool result = (IsDerivedFrom(record, object_decl_) &&
1361 !IsDerivedFrom(record, smi_decl_)) ||
1362 IsDerivedFrom(record, maybe_object_decl_);
1363 return result;
1364 }
1365
IsRawPointerType(const clang::PointerType * type)1366 bool IsRawPointerType(const clang::PointerType* type) {
1367 const clang::CXXRecordDecl* record = type->getPointeeCXXRecordDecl();
1368 bool result = IsDerivedFromInternalPointer(record);
1369 TRACE("is raw " << result << " " << record->getNameAsString());
1370 return result;
1371 }
1372
IsInternalPointerType(clang::QualType qtype)1373 bool IsInternalPointerType(clang::QualType qtype) {
1374 const clang::CXXRecordDecl* record = qtype->getAsCXXRecordDecl();
1375 bool result = IsDerivedFromInternalPointer(record);
1376 TRACE_LLVM_TYPE("is internal " << result, qtype);
1377 return result;
1378 }
1379
1380 // Returns weather the given type is a raw pointer or a wrapper around
1381 // such. For V8 that means Object and MaybeObject instances.
RepresentsRawPointerType(clang::QualType qtype)1382 bool RepresentsRawPointerType(clang::QualType qtype) {
1383 // Not yet assigned pointers can't get moved by the GC.
1384 if (qtype.isNull()) {
1385 return false;
1386 }
1387 // nullptr can't get moved by the GC.
1388 if (qtype->isNullPtrType()) {
1389 return false;
1390 }
1391
1392 const clang::PointerType* pointer_type =
1393 llvm::dyn_cast_or_null<clang::PointerType>(qtype.getTypePtrOrNull());
1394 if (pointer_type != NULL) {
1395 return IsRawPointerType(pointer_type);
1396 } else {
1397 return IsInternalPointerType(qtype);
1398 }
1399 }
1400
IsGCGuard(clang::QualType qtype)1401 bool IsGCGuard(clang::QualType qtype) {
1402 if (qtype.isNull()) {
1403 return false;
1404 }
1405 if (qtype->isNullPtrType()) {
1406 return false;
1407 }
1408
1409 const clang::CXXRecordDecl* record = qtype->getAsCXXRecordDecl();
1410 const clang::CXXRecordDecl* definition = GetDefinitionOrNull(record);
1411
1412 if (!definition) {
1413 return false;
1414 }
1415
1416 return (no_gc_decl_ && IsDerivedFrom(definition, no_gc_decl_)) ||
1417 (no_gc_or_safepoint_decl_ &&
1418 IsDerivedFrom(definition, no_gc_or_safepoint_decl_)) ||
1419 (no_heap_access_decl_ &&
1420 IsDerivedFrom(definition, no_heap_access_decl_));
1421 }
1422
VisitDecl(clang::Decl * decl,Environment & env)1423 Environment VisitDecl(clang::Decl* decl, Environment& env) {
1424 if (clang::VarDecl* var = llvm::dyn_cast<clang::VarDecl>(decl)) {
1425 Environment out = var->hasInit() ? VisitStmt(var->getInit(), env) : env;
1426
1427 if (RepresentsRawPointerType(var->getType())) {
1428 out = out.Define(var->getNameAsString());
1429 }
1430 if (IsGCGuard(var->getType())) {
1431 scopes_.back().guard_location =
1432 clang::FullSourceLoc(decl->getLocation(), sm_);
1433 }
1434
1435 return out;
1436 }
1437 // TODO(gcmole): handle other declarations?
1438 return env;
1439 }
1440
DECL_VISIT_STMT(DeclStmt)1441 DECL_VISIT_STMT(DeclStmt) {
1442 Environment out = env;
1443 clang::DeclStmt::decl_iterator end = stmt->decl_end();
1444 for (clang::DeclStmt::decl_iterator decl = stmt->decl_begin();
1445 decl != end;
1446 ++decl) {
1447 out = VisitDecl(*decl, out);
1448 }
1449 return out;
1450 }
1451
1452
DefineParameters(const clang::FunctionDecl * f,Environment * env)1453 void DefineParameters(const clang::FunctionDecl* f,
1454 Environment* env) {
1455 env->MDefine(THIS);
1456 clang::FunctionDecl::param_const_iterator end = f->param_end();
1457 for (clang::FunctionDecl::param_const_iterator p = f->param_begin();
1458 p != end;
1459 ++p) {
1460 env->MDefine((*p)->getNameAsString());
1461 }
1462 }
1463
1464
AnalyzeFunction(const clang::FunctionDecl * f)1465 void AnalyzeFunction(const clang::FunctionDecl* f) {
1466 const clang::FunctionDecl* body = NULL;
1467 if (f->hasBody(body)) {
1468 Environment env;
1469 DefineParameters(body, &env);
1470 VisitStmt(body->getBody(), env);
1471 Environment::ClearSymbolTable();
1472 }
1473 }
1474
EnterBlock(Block * block)1475 Block* EnterBlock(Block* block) {
1476 Block* parent = block_;
1477 block_ = block;
1478 return parent;
1479 }
1480
LeaveBlock(Block * block)1481 void LeaveBlock(Block* block) {
1482 block_ = block;
1483 }
1484
HasActiveGuard()1485 bool HasActiveGuard() {
1486 for (auto s : scopes_) {
1487 if (s.IsBeforeGCCause()) return true;
1488 }
1489 return false;
1490 }
1491
1492 private:
ReportUnsafe(const clang::Expr * expr,const std::string & msg)1493 void ReportUnsafe(const clang::Expr* expr, const std::string& msg) {
1494 d_.Report(clang::FullSourceLoc(expr->getExprLoc(), sm_),
1495 d_.getCustomDiagID(clang::DiagnosticsEngine::Warning, "%0"))
1496 << msg;
1497 }
1498
1499
1500 clang::MangleContext* ctx_;
1501 clang::CXXRecordDecl* object_decl_;
1502 clang::CXXRecordDecl* maybe_object_decl_;
1503 clang::CXXRecordDecl* smi_decl_;
1504 clang::CXXRecordDecl* no_gc_decl_;
1505 clang::CXXRecordDecl* no_gc_or_safepoint_decl_;
1506 clang::CXXRecordDecl* no_heap_access_decl_;
1507
1508 clang::DiagnosticsEngine& d_;
1509 clang::SourceManager& sm_;
1510
1511 Block* block_;
1512
1513 struct GCScope {
1514 clang::FullSourceLoc guard_location;
1515 clang::FullSourceLoc gccause_location;
1516
1517 // We're only interested in guards that are declared before any further GC
1518 // causing calls (see TestGuardedDeadVarAnalysisMidFunction for example).
IsBeforeGCCause__anon79c686130111::FunctionAnalyzer::GCScope1519 bool IsBeforeGCCause() {
1520 if (!guard_location.isValid()) return false;
1521 if (!gccause_location.isValid()) return true;
1522 return guard_location.isBeforeInTranslationUnitThan(gccause_location);
1523 }
1524
1525 // After we set the first GC cause in the scope, we don't need the later
1526 // ones.
SetGCCauseLocation__anon79c686130111::FunctionAnalyzer::GCScope1527 void SetGCCauseLocation(clang::FullSourceLoc gccause_location_) {
1528 if (gccause_location.isValid()) return;
1529 gccause_location = gccause_location_;
1530 }
1531 };
1532 std::vector<GCScope> scopes_;
1533 };
1534
1535 class ProblemsFinder : public clang::ASTConsumer,
1536 public clang::RecursiveASTVisitor<ProblemsFinder> {
1537 public:
ProblemsFinder(clang::DiagnosticsEngine & d,clang::SourceManager & sm,const std::vector<std::string> & args)1538 ProblemsFinder(clang::DiagnosticsEngine& d, clang::SourceManager& sm,
1539 const std::vector<std::string>& args)
1540 : d_(d), sm_(sm) {
1541 for (unsigned i = 0; i < args.size(); ++i) {
1542 if (args[i] == "--dead-vars") {
1543 g_dead_vars_analysis = true;
1544 }
1545 if (args[i] == "--verbose") {
1546 g_tracing_enabled = true;
1547 }
1548 }
1549 }
1550
TranslationUnitIgnored()1551 bool TranslationUnitIgnored() {
1552 if (!ignored_files_loaded_) {
1553 std::ifstream fin("tools/gcmole/ignored_files");
1554 std::string s;
1555 while (fin >> s) ignored_files_.insert(s);
1556 ignored_files_loaded_ = true;
1557 }
1558
1559 clang::FileID main_file_id = sm_.getMainFileID();
1560 std::string filename = sm_.getFileEntryForID(main_file_id)->getName().str();
1561
1562 bool result = ignored_files_.find(filename) != ignored_files_.end();
1563 if (result) {
1564 llvm::outs() << "Ignoring file " << filename << "\n";
1565 }
1566 return result;
1567 }
1568
HandleTranslationUnit(clang::ASTContext & ctx)1569 virtual void HandleTranslationUnit(clang::ASTContext &ctx) {
1570 if (TranslationUnitIgnored()) {
1571 return;
1572 }
1573
1574 Resolver r(ctx);
1575
1576 // It is a valid situation that no_gc_decl == NULL when the
1577 // DisallowHeapAllocation is not included and can't be resolved.
1578 // This is gracefully handled in the FunctionAnalyzer later.
1579 clang::CXXRecordDecl* no_gc_decl =
1580 r.ResolveNamespace("v8")
1581 .ResolveNamespace("internal")
1582 .ResolveTemplate("DisallowHeapAllocation");
1583
1584 clang::CXXRecordDecl* no_gc_or_safepoint_decl =
1585 r.ResolveNamespace("v8")
1586 .ResolveNamespace("internal")
1587 .ResolveTemplate("DisallowGarbageCollection");
1588
1589 clang::CXXRecordDecl* no_heap_access_decl =
1590 r.ResolveNamespace("v8")
1591 .ResolveNamespace("internal")
1592 .Resolve<clang::CXXRecordDecl>("DisallowHeapAccess");
1593
1594 clang::CXXRecordDecl* object_decl =
1595 r.ResolveNamespace("v8").ResolveNamespace("internal").
1596 Resolve<clang::CXXRecordDecl>("Object");
1597
1598 clang::CXXRecordDecl* maybe_object_decl =
1599 r.ResolveNamespace("v8")
1600 .ResolveNamespace("internal")
1601 .Resolve<clang::CXXRecordDecl>("MaybeObject");
1602
1603 clang::CXXRecordDecl* smi_decl =
1604 r.ResolveNamespace("v8").ResolveNamespace("internal").
1605 Resolve<clang::CXXRecordDecl>("Smi");
1606
1607 if (object_decl != NULL) object_decl = object_decl->getDefinition();
1608
1609 if (maybe_object_decl != NULL)
1610 maybe_object_decl = maybe_object_decl->getDefinition();
1611
1612 if (smi_decl != NULL) smi_decl = smi_decl->getDefinition();
1613
1614 if (no_heap_access_decl != NULL)
1615 no_heap_access_decl = no_heap_access_decl->getDefinition();
1616
1617 if (object_decl != NULL && smi_decl != NULL && maybe_object_decl != NULL) {
1618 function_analyzer_ = new FunctionAnalyzer(
1619 clang::ItaniumMangleContext::create(ctx, d_), object_decl,
1620 maybe_object_decl, smi_decl, no_gc_decl, no_gc_or_safepoint_decl,
1621 no_heap_access_decl, d_, sm_);
1622 TraverseDecl(ctx.getTranslationUnitDecl());
1623 } else {
1624 if (object_decl == NULL) {
1625 llvm::errs() << "Failed to resolve v8::internal::Object\n";
1626 }
1627 if (maybe_object_decl == NULL) {
1628 llvm::errs() << "Failed to resolve v8::internal::MaybeObject\n";
1629 }
1630 if (smi_decl == NULL) {
1631 llvm::errs() << "Failed to resolve v8::internal::Smi\n";
1632 }
1633 }
1634 }
1635
VisitFunctionDecl(clang::FunctionDecl * decl)1636 virtual bool VisitFunctionDecl(clang::FunctionDecl* decl) {
1637 // Don't print tracing from includes, otherwise the output is too big.
1638 bool tracing = g_tracing_enabled;
1639 const auto& fileID = sm_.getFileID(decl->getLocation());
1640 if (fileID != sm_.getMainFileID()) {
1641 g_tracing_enabled = false;
1642 }
1643
1644 TRACE("Visiting function " << decl->getNameAsString());
1645 function_analyzer_->AnalyzeFunction(decl);
1646
1647 g_tracing_enabled = tracing;
1648 return true;
1649 }
1650
1651 private:
1652 clang::DiagnosticsEngine& d_;
1653 clang::SourceManager& sm_;
1654
1655 bool ignored_files_loaded_ = false;
1656 std::set<std::string> ignored_files_;
1657
1658 FunctionAnalyzer* function_analyzer_;
1659 };
1660
1661
1662 template<typename ConsumerType>
1663 class Action : public clang::PluginASTAction {
1664 protected:
CreateASTConsumer(clang::CompilerInstance & CI,llvm::StringRef InFile)1665 virtual std::unique_ptr<clang::ASTConsumer> CreateASTConsumer(
1666 clang::CompilerInstance& CI, llvm::StringRef InFile) {
1667 return std::unique_ptr<clang::ASTConsumer>(
1668 new ConsumerType(CI.getDiagnostics(), CI.getSourceManager(), args_));
1669 }
1670
ParseArgs(const clang::CompilerInstance & CI,const std::vector<std::string> & args)1671 bool ParseArgs(const clang::CompilerInstance &CI,
1672 const std::vector<std::string>& args) {
1673 args_ = args;
1674 return true;
1675 }
1676
PrintHelp(llvm::raw_ostream & ros)1677 void PrintHelp(llvm::raw_ostream& ros) {
1678 }
1679 private:
1680 std::vector<std::string> args_;
1681 };
1682
1683
1684 }
1685
1686 static clang::FrontendPluginRegistry::Add<Action<ProblemsFinder> >
1687 FindProblems("find-problems", "Find GC-unsafe places.");
1688
1689 static clang::FrontendPluginRegistry::Add<
1690 Action<FunctionDeclarationFinder> >
1691 DumpCallees("dump-callees", "Dump callees for each function.");
1692
1693 #undef TRACE
1694 #undef TRACE_LLVM_TYPE
1695 #undef TRACE_LLVM_DECL
1696 #undef DECL_VISIT_EXPR
1697 #undef IGNORE_EXPR
1698 #undef DECL_VISIT_STMT
1699 #undef IGNORE_STMT
1700