[gcmole] Avoid hardcoded maximum of 256 locals

tools/gcmole/gcmole.cc

 // Copyright 2011 the V8 project authors. All rights reserved.
 // Redistribution and use in source and binary forms, with or without
 // modification, are permitted provided that the following conditions are
 // met:
 //
 //     * Redistributions of source code must retain the above copyright
 //       notice, this list of conditions and the following disclaimer.
 //     * Redistributions in binary form must reproduce the above
 //       copyright notice, this list of conditions and the following
 //       disclaimer in the documentation and/or other materials provided
@@ skipping 300 matching lines @@
   intptr_t effect_;
 };
 
 
 const std::string BAD_EXPR_MSG("Possible problem with evaluation order.");
 const std::string DEAD_VAR_MSG("Possibly dead variable.");
 
 
 class Environment {
  public:
-  Environment() { }
+  Environment() = default;
 
   static Environment Unreachable() {
     Environment env;
-    env.live_.set();
+    env.unreachable_ = true;
     return env;
   }
 
   static Environment Merge(const Environment& l,
                            const Environment& r) {
-    return Environment(l, r);
+    Environment out(l);
+    out &= r;
+    return out;
   }
 
   Environment ApplyEffect(ExprEffect effect) const {
     Environment out = effect.hasGC() ? Environment() : Environment(*this);
-    if (effect.env() != NULL) out.live_ |= effect.env()->live_;
+    if (effect.env()) out |= *effect.env();
     return out;
   }
 
   typedef std::map<std::string, int> SymbolTable;
 
   bool IsAlive(const std::string& name) const {
     SymbolTable::iterator code = symbol_table_.find(name);
     if (code == symbol_table_.end()) return false;
-    return live_[code->second];
+    return is_live(code->second);
   }
 
   bool Equal(const Environment& env) {
-    return live_ == env.live_;
+    if (unreachable_) return env.unreachable_;

[Michael Achenbach, 2017/02/15 15:13:13]

So, there's an invariant that if unreachable==true live_ is empty? Maybe that
should be asserted somewhere?

[Clemens Hammacher, 2017/02/15 15:19:55]

If unreachable==true, then is_live always returns true, just as in the old
implementation. Hence there is no point in running the further checks.

[Vyacheslav Egorov (Google), 2017/02/15 15:48:15]

This does not seem correct. 

We have: env.unreachable_ implies forall i . env.is_alive(i)

However we don't have implication in the opposite direction:

forall i . env.is_alive(i) does not imply env.unreachable_

Which means you can have an environment where unreachable_ is false but all bits
are still set so it compares true to an environment which has unreachable_ set.

[Vyacheslav Egorov (Google), 2017/02/15 15:59:37]

Clarification:

environment where unreachable_ is false but all bits are still set must compare
equal to an environment which has unreachable_ set to true. 

This code does not handle it correctly.

+    size_t size = std::max(live_.size(), env.live_.size());

[Michael Achenbach, 2017/02/15 15:13:13]

Maybe return false early if size differs?

[Clemens Hammacher, 2017/02/15 15:19:54]

That would be a stronger check than before. In this implementation, I just check
that the same locals are live.
I did not try to fully understand the implementation, I tried to be semantically
equivalent to the previous implementation.

[Michael Starzinger, 2017/02/15 15:20:12]

Wouldn't that change semantics? If the size is different but the tail of the
longer vector has all {false}, the two vectors should still compare as being
equal IMHO.

+    for (size_t i = 0; i < size; ++i) {
+      if (is_live(i) != env.is_live(i)) return false;
+    }
+    return true;
   }
 
   Environment Define(const std::string& name) const {
     return Environment(*this, SymbolToCode(name));
   }
 
-  void MDefine(const std::string& name) {
-    live_.set(SymbolToCode(name));
-  }
+  void MDefine(const std::string& name) { set_live(SymbolToCode(name)); }
 
   static int SymbolToCode(const std::string& name) {
     SymbolTable::iterator code = symbol_table_.find(name);
 
     if (code == symbol_table_.end()) {
       int new_code = symbol_table_.size();
       symbol_table_.insert(std::make_pair(name, new_code));
       return new_code;
     }
 
     return code->second;
   }
 
   static void ClearSymbolTable() {
-    std::vector<Environment*>::iterator end = envs_.end();
-    for (std::vector<Environment*>::iterator i = envs_.begin();
-         i != end;
-         ++i) {
-      delete *i;
-    }
+    for (Environment* e : envs_) delete e;
     envs_.clear();
     symbol_table_.clear();
   }
 
   void Print() const {
     bool comma = false;
     std::cout << "{";
-    SymbolTable::iterator end = symbol_table_.end();
-    for (SymbolTable::iterator i = symbol_table_.begin();
-         i != end;
-         ++i) {
-      if (live_[i->second]) {
-        if (comma) std::cout << ", ";
-        std::cout << i->first;
-        comma = true;
-      }
+    for (auto& e : symbol_table_) {
+      if (!is_live(e.second)) continue;
+      if (comma) std::cout << ", ";
+      std::cout << e.first;
+      comma = true;
     }
     std::cout << "}";
   }
 
   static Environment* Allocate(const Environment& env) {
     Environment* allocated_env = new Environment(env);
     envs_.push_back(allocated_env);
     return allocated_env;
   }
 
  private:
-  Environment(const Environment& l, const Environment& r)
-      : live_(l.live_ & r.live_) {
+  Environment(const Environment& l, int code)
+      : live_(l.live_) {
+    set_live(code);
   }
 
-  Environment(const Environment& l, int code)
-      : live_(l.live_) {
-    live_.set(code);
+  void set_live(size_t pos) {
+    if (live_.size() <= pos) live_.resize(std::max(pos + 1, 2 * live_.size()));
+    live_[pos] = true;
+  }
+
+  bool is_live(size_t pos) const {
+    return unreachable_ || (live_.size() > pos && live_[pos]);
+  }
+
+  Environment& operator|=(const Environment& o) {
+    unreachable_ |= o.unreachable_;
+    for (size_t i = 0, e = o.live_.size(); i < e; ++i) {

[Vyacheslav Egorov (Google), 2017/02/15 15:59:36]

if one of the envs is unreachable we should just make live_ empty and ignore it.
no reason to populate o.live_ in an inconsistent manner (all of them must be
true to be consistent with unreachable_).

because if at some point unreachable_ will be set to false (like for example
below in operator&) then we will start using inconsistent live_ and arrive to
very confusing results. 

+      if (o.live_[i]) set_live(i);
+    }
+    return *this;
+  }
+
+  Environment& operator&=(const Environment& o) {
+    unreachable_ &= o.unreachable_;
+    size_t size = std::min(live_.size(), o.live_.size());

[Vyacheslav Egorov (Google), 2017/02/15 15:48:15]

This seems highly suspicious: 

if o.unreachable_ then o.live_.size() can very well be 0, in which case we will
just drop all the bits into oblivion.  

[Vyacheslav Egorov (Google), 2017/02/15 15:59:36]

Clarification: the same problem with o and this. It must take unreachable_ into
account when merging live_. 

If this is unreachable and o is not: *this = o;
if o is unreachable: do nothing. 

+    if (live_.size() > size) live_.resize(size);
+    for (size_t i = 0; i < size; ++i) {
+      if (live_[i] && (i > o.live_.size() || !o.live_[i])) live_[i] = false;
+    }
+    return *this;
   }
 
   static SymbolTable symbol_table_;
-  static std::vector<Environment* > envs_;
+  static std::vector<Environment*> envs_;
 
-  static const int kMaxNumberOfLocals = 256;
-  std::bitset<kMaxNumberOfLocals> live_;
+  std::vector<bool> live_;
+  bool unreachable_ = false;
 
   friend class ExprEffect;
   friend class CallProps;
 };
 
 
 class CallProps {
  public:
   CallProps() : env_(NULL) { }
 
   void SetEffect(int arg, ExprEffect in) {
     if (in.hasGC()) gc_.set(arg);
     if (in.hasRawDef()) raw_def_.set(arg);
     if (in.hasRawUse()) raw_use_.set(arg);
     if (in.env() != NULL) {
-      if (env_ == NULL) env_ = in.env();
-      env_->live_ |= in.env()->live_;
+      if (env_ == NULL) {
+        env_ = in.env();
+      } else {
+        *env_ |= *in.env();
+      }
     }
   }
 
   ExprEffect ComputeCumulativeEffect(bool result_is_raw) {
     ExprEffect out = ExprEffect::NoneWithEnv(env_);
     if (gc_.any()) out.setGC();
     if (raw_use_.any()) out.setRawUse();
     if (result_is_raw) out.setRawDef();
     return out;
   }
 
   bool IsSafe() {
     if (!gc_.any()) return true;
     std::bitset<kMaxNumberOfArguments> raw = (raw_def_ | raw_use_);
     if (!raw.any()) return true;
     return gc_.count() == 1 && !((raw ^ gc_).any());
   }
 
  private:
   static const int kMaxNumberOfArguments = 64;
   std::bitset<kMaxNumberOfArguments> raw_def_;
   std::bitset<kMaxNumberOfArguments> raw_use_;
   std::bitset<kMaxNumberOfArguments> gc_;
   Environment* env_;
 };
 
 
 Environment::SymbolTable Environment::symbol_table_;
-std::vector<Environment* > Environment::envs_;
-
+std::vector<Environment*> Environment::envs_;
 
 ExprEffect ExprEffect::Merge(ExprEffect a, ExprEffect b) {
   Environment* a_env = a.env();
   Environment* b_env = b.env();
   Environment* out = NULL;
   if (a_env != NULL && b_env != NULL) {
     out = Environment::Allocate(*a_env);
-    out->live_ &= b_env->live_;
+    *out &= *b_env;
   }
   return ExprEffect(a.effect_ | b.effect_, out);
 }
 
 
 ExprEffect ExprEffect::MergeSeq(ExprEffect a, ExprEffect b) {
   Environment* a_env = b.hasGC() ? NULL : a.env();
   Environment* b_env = b.env();
   Environment* out = (b_env == NULL) ? a_env : b_env;
   if (a_env != NULL && b_env != NULL) {
     out = Environment::Allocate(*b_env);
-    out->live_ |= a_env->live_;
+    *out |= *a_env;
   }
   return ExprEffect(a.effect_ | b.effect_, out);
 }
 
 
 ExprEffect ExprEffect::Define(const std::string& name) {
   Environment* e = env();
   if (e == NULL) {
     e = Environment::Allocate(Environment());
   }
@@ skipping 761 matching lines @@
 
 
 }
 
 static clang::FrontendPluginRegistry::Add<Action<ProblemsFinder> >
 FindProblems("find-problems", "Find GC-unsafe places.");
 
 static clang::FrontendPluginRegistry::Add<
   Action<FunctionDeclarationFinder> >
 DumpCallees("dump-callees", "Dump callees for each function.");