[gcmole] Avoid hardcoded maximum of 256 locals

tools/gcmole/gcmole.cc

Index: tools/gcmole/gcmole.cc
diff --git a/tools/gcmole/gcmole.cc b/tools/gcmole/gcmole.cc
index 9f1f781453d54bf121109d11f1f3406bfc058524..67f676d667165fe1f3c5baa8f4f5d3ede21d2218 100644
--- a/tools/gcmole/gcmole.cc
+++ b/tools/gcmole/gcmole.cc
@@ -318,22 +318,24 @@ 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;
   }
 
@@ -342,20 +344,23 @@ class Environment {
   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);
@@ -370,12 +375,7 @@ class Environment {
   }
 
   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();
   }
@@ -383,15 +383,11 @@ class Environment {
   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 << "}";
   }
@@ -403,20 +399,43 @@ class Environment {
   }
 
  private:
-  Environment(const Environment& l, const Environment& r)
-      : live_(l.live_ & r.live_) {
-  }
-
   Environment(const Environment& l, int code)
       : live_(l.live_) {
-    live_.set(code);
+    set_live(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;
@@ -432,8 +451,11 @@ class CallProps {
     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();
+      }
     }
   }
 
@@ -462,8 +484,7 @@ class CallProps {
 
 
 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();
@@ -471,7 +492,7 @@ ExprEffect ExprEffect::Merge(ExprEffect a, ExprEffect b) {
   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);
 }
@@ -483,7 +504,7 @@ ExprEffect ExprEffect::MergeSeq(ExprEffect a, ExprEffect b) {
   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);
 }