[gcmole] Avoid hardcoded maximum of 256 locals

[gcmole] Avoid hardcoded maximum of 256 locals

This CL changes the datastructure to store live variables from a
std::bitset<256> to a std::vector<bool> to support an arbitrary number
of locals. Unfortunately, std::vector<bool> does not define |= and &=
operators, so I added them on the Environment class.

R=vegorov@chromium.org, mstarzinger@chromium.org, machenbach@chromium.org
BUG=v8:5970
Review-Url: https://codereview.chromium.org/2694103005
Cr-Commit-Position: refs/heads/master@{#43216}
Committed: https://chromium.googlesource.com/v8/v8/+/b8787e348de92d70d9a7c226cf82d8a95a6dada4

[Clemens Hammacher, 2017-02-15 13:03:33]

The CQ bit was checked by clemensh@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2017-02-15 13:03:36]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2017-02-15 13:31:48]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2017-02-15 13:31:49]

Dry run: This issue passed the CQ dry run.

[Michael Starzinger, 2017-02-15 13:41:21]

LGTM.

[Clemens Hammacher, 2017-02-15 14:41:43]

The CQ bit was checked by clemensh@chromium.org

[commit-bot: I haz the power, 2017-02-15 14:41:47]

CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2017-02-15 14:43:23]

CQ is committing da patch.

Bot data: {"patchset_id": 1, "attempt_start_ts": 1487169703372640, "parent_rev":
"3fc10464e16d058dd7a637da6ebe37d5005b5d78", "commit_rev":
"b8787e348de92d70d9a7c226cf82d8a95a6dada4"}

[commit-bot: I haz the power, 2017-02-15 14:43:27]

Description was changed from

==========
[gcmole] Avoid hardcoded maximum of 256 locals

This CL changes the datastructure to store live variables from a
std::bitset<256> to a std::vector<bool> to support an arbitrary number
of locals. Unfortunately, std::vector<bool> does not define |= and &=
operators, so I added them on the Environment class.

R=vegorov@chromium.org, mstarzinger@chromium.org, machenbach@chromium.org
BUG=v8:5970
==========

to

==========
[gcmole] Avoid hardcoded maximum of 256 locals

This CL changes the datastructure to store live variables from a
std::bitset<256> to a std::vector<bool> to support an arbitrary number
of locals. Unfortunately, std::vector<bool> does not define |= and &=
operators, so I added them on the Environment class.

R=vegorov@chromium.org, mstarzinger@chromium.org, machenbach@chromium.org
BUG=v8:5970

Review-Url: https://codereview.chromium.org/2694103005
Cr-Commit-Position: refs/heads/master@{#43216}
Committed:
https://chromium.googlesource.com/v8/v8/+/b8787e348de92d70d9a7c226cf82d8a95a6...
==========

[commit-bot: I haz the power, 2017-02-15 14:43:28]

Committed patchset #1 (id:1) as
https://chromium.googlesource.com/v8/v8/+/b8787e348de92d70d9a7c226cf82d8a95a6...

[Michael Achenbach, 2017-02-15 15:13:14]

lgtm

https://codereview.chromium.org/2694103005/diff/1/tools/gcmole/gcmole.cc
File tools/gcmole/gcmole.cc (right):

https://codereview.chromium.org/2694103005/diff/1/tools/gcmole/gcmole.cc#newc...
tools/gcmole/gcmole.cc:351: if (unreachable_) return env.unreachable_;
So, there's an invariant that if unreachable==true live_ is empty? Maybe that
should be asserted somewhere?

https://codereview.chromium.org/2694103005/diff/1/tools/gcmole/gcmole.cc#newc...
tools/gcmole/gcmole.cc:352: size_t size = std::max(live_.size(),
env.live_.size());
Maybe return false early if size differs?

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

https://codereview.chromium.org/2694103005/diff/1/tools/gcmole/gcmole.cc
File tools/gcmole/gcmole.cc (right):

https://codereview.chromium.org/2694103005/diff/1/tools/gcmole/gcmole.cc#newc...
tools/gcmole/gcmole.cc:351: if (unreachable_) return env.unreachable_;
On 2017/02/15 at 15:13:13, Michael Achenbach wrote:
> So, there's an invariant that if unreachable==true live_ is empty? Maybe that
should be asserted somewhere?

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.

https://codereview.chromium.org/2694103005/diff/1/tools/gcmole/gcmole.cc#newc...
tools/gcmole/gcmole.cc:352: size_t size = std::max(live_.size(),
env.live_.size());
On 2017/02/15 at 15:13:13, Michael Achenbach wrote:
> Maybe return false early if size differs?

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]

https://codereview.chromium.org/2694103005/diff/1/tools/gcmole/gcmole.cc
File tools/gcmole/gcmole.cc (right):

https://codereview.chromium.org/2694103005/diff/1/tools/gcmole/gcmole.cc#newc...
tools/gcmole/gcmole.cc:352: size_t size = std::max(live_.size(),
env.live_.size());
On 2017/02/15 15:13:13, Michael Achenbach wrote:
> Maybe return false early if size differs?

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.

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

vegorov@google.com changed reviewers:
+ vegorov@google.com

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

https://codereview.chromium.org/2694103005/diff/1/tools/gcmole/gcmole.cc
File tools/gcmole/gcmole.cc (right):

https://codereview.chromium.org/2694103005/diff/1/tools/gcmole/gcmole.cc#newc...
tools/gcmole/gcmole.cc:351: if (unreachable_) return env.unreachable_;
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.

https://codereview.chromium.org/2694103005/diff/1/tools/gcmole/gcmole.cc#newc...
tools/gcmole/gcmole.cc:426: size_t size = std::min(live_.size(),
o.live_.size());
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:37]

Few clarification for my comments.

https://codereview.chromium.org/2694103005/diff/1/tools/gcmole/gcmole.cc
File tools/gcmole/gcmole.cc (right):

https://codereview.chromium.org/2694103005/diff/1/tools/gcmole/gcmole.cc#newc...
tools/gcmole/gcmole.cc:351: if (unreachable_) return env.unreachable_;
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.

https://codereview.chromium.org/2694103005/diff/1/tools/gcmole/gcmole.cc#newc...
tools/gcmole/gcmole.cc:418: for (size_t i = 0, e = o.live_.size(); i < e; ++i) {
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.

https://codereview.chromium.org/2694103005/diff/1/tools/gcmole/gcmole.cc#newc...
tools/gcmole/gcmole.cc:426: size_t size = std::min(live_.size(),
o.live_.size());
On 2017/02/15 15:48:15, Vyacheslav Egorov (Google) wrote:
> 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.  

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.

[Clemens Hammacher, 2017-02-16 11:24:14]

Thanks for the comments. Totally makes sense.
This CL should fix the issues: http://crrev.com/2691103008

I also did some measurements to ensure that this change (together with the
fixup) does not degrade performance of gcmole.
Result: no observable difference.
old:
python run-gcmole.py ia32  3455.42s user 139.69s system 4394% cpu 1:21.81 total
new:
python run-gcmole.py ia32  3472.03s user 137.05s system 4449% cpu 1:21.11 total