[turbofan] Unit tests for live range conflicts.

Unit tests for the live range conflict detection mechanism (CoalescedLiveRanges) in the Greedy Allocator.

Consolidated conflict detection and traversal logic in CoalescedLiveRanges to avoid duplication in both code and testing. In addition, this change achieves better separation between CoalescedLiveRanges and other register allocator components, improving testability and maintainability.

BUG=

Committed: https://crrev.com/3e3608cdd5073965491db95b1fa085db506d468d
Cr-Commit-Position: refs/heads/master@{#29783}

[Mircea Trofin, 2015-07-08 18:11:16]

Patchset #5 (id:80001) has been deleted

[Mircea Trofin, 2015-07-08 18:11:24]

Patchset #5 (id:100001) has been deleted

[Mircea Trofin, 2015-07-08 18:11:29]

Patchset #4 (id:60001) has been deleted

[Mircea Trofin, 2015-07-08 18:12:12]

Patchset #1 (id:1) has been deleted

[Mircea Trofin, 2015-07-08 18:12:23]

Patchset #1 (id:20001) has been deleted

[Mircea Trofin, 2015-07-08 18:12:30]

Patchset #1 (id:40001) has been deleted

[Mircea Trofin, 2015-07-08 20:03:00]

mtrofin@chromium.org changed reviewers:
+ bmeurer@chromium.org, jarin@chromium.org

[Benedikt Meurer, 2015-07-13 05:01:25]

https://codereview.chromium.org/1219063017/diff/120001/test/unittests/compile...
File test/unittests/compiler/coalesced-live-ranges-unittest.cc (right):

https://codereview.chromium.org/1219063017/diff/120001/test/unittests/compile...
test/unittests/compiler/coalesced-live-ranges-unittest.cc:24: TestRangeBuilder&
operator()(int start, int end) {
Operator overloading is strongly discouraged. Please just use an Add method for
that.

https://codereview.chromium.org/1219063017/diff/120001/test/unittests/compile...
test/unittests/compiler/coalesced-live-ranges-unittest.cc:28: operator
LiveRange*() {
How about a Build method instead?

[Mircea Trofin, 2015-07-13 16:54:08]

https://codereview.chromium.org/1219063017/diff/120001/test/unittests/compile...
File test/unittests/compiler/coalesced-live-ranges-unittest.cc (right):

https://codereview.chromium.org/1219063017/diff/120001/test/unittests/compile...
test/unittests/compiler/coalesced-live-ranges-unittest.cc:24: TestRangeBuilder&
operator()(int start, int end) {
On 2015/07/13 05:01:25, Benedikt Meurer wrote:
> Operator overloading is strongly discouraged. Please just use an Add method
for
> that.

Done.

https://codereview.chromium.org/1219063017/diff/120001/test/unittests/compile...
test/unittests/compiler/coalesced-live-ranges-unittest.cc:28: operator
LiveRange*() {
On 2015/07/13 05:01:25, Benedikt Meurer wrote:
> How about a Build method instead?

Done.

[Benedikt Meurer, 2015-07-14 04:35:01]

https://codereview.chromium.org/1219063017/diff/140001/test/unittests/compile...
File test/unittests/compiler/coalesced-live-ranges-unittest.cc (right):

https://codereview.chromium.org/1219063017/diff/140001/test/unittests/compile...
test/unittests/compiler/coalesced-live-ranges-unittest.cc:64: Conflicts(int
number_of_conflicts, ...) : set_() {
Do we really need to use varargs here? You could apply the builder pattern again
instead.

https://codereview.chromium.org/1219063017/diff/140001/test/unittests/compile...
test/unittests/compiler/coalesced-live-ranges-unittest.cc:75: operator
LiveRangeIDs&() { return set_; }
Same here, there's no need for operator overloading.

[Benedikt Meurer, 2015-07-14 05:13:04]

https://codereview.chromium.org/1219063017/diff/140001/src/compiler/coalesced...
File src/compiler/coalesced-live-ranges.h (right):

https://codereview.chromium.org/1219063017/diff/140001/src/compiler/coalesced...
src/compiler/coalesced-live-ranges.h:38: void VisitConflicts(const LiveRange*
range, ConstLiveRangePtrToBool visitor) {
Higher order functions which iterate over a data structure, and allow callbacks
to mutate the underlying data structure, are usually a bad idea, esp. in C++
(with STL). IMHO this is worse compared to the conflict_iterator.

What happened to the idea of simple loops? I thought we agreed on that as a
starting point.

[Mircea Trofin, 2015-07-14 15:21:07]

https://codereview.chromium.org/1219063017/diff/140001/src/compiler/coalesced...
File src/compiler/coalesced-live-ranges.h (right):

https://codereview.chromium.org/1219063017/diff/140001/src/compiler/coalesced...
src/compiler/coalesced-live-ranges.h:38: void VisitConflicts(const LiveRange*
range, ConstLiveRangePtrToBool visitor) {
On 2015/07/14 05:13:04, Benedikt Meurer wrote:
> Higher order functions which iterate over a data structure, and allow
callbacks
> to mutate the underlying data structure, are usually a bad idea, esp. in C++
> (with STL). IMHO this is worse compared to the conflict_iterator.
> 
> What happened to the idea of simple loops? I thought we agreed on that as a
> starting point.

I called this out in the code review description: the starting point suffered
from code duplication and increased concept coupling. Both complicate (and
increase cost of) maintenance and testing.

The starting point wasn't really simple loops either: both
GetMaximumConflictingWeight and EvictAndRescheduleConflicts had to carefully
traverse the set of allocated ranges, and in a very similar way. The difference
between the 2 was subtle and unnecessary (eviction had to skip over successive
intervals of same range, finding max weight could do without that, but didn't
need to). When looking into unit testing, the code duplication became clear.

I'm assuming your concern with potentially mutating visitors is about mutation
invalidating the underlying iterator? I believe the implementation ensures safe
mutation, unless I'm missing something?

[Mircea Trofin, 2015-07-14 16:19:18]

https://codereview.chromium.org/1219063017/diff/140001/test/unittests/compile...
File test/unittests/compiler/coalesced-live-ranges-unittest.cc (right):

https://codereview.chromium.org/1219063017/diff/140001/test/unittests/compile...
test/unittests/compiler/coalesced-live-ranges-unittest.cc:64: Conflicts(int
number_of_conflicts, ...) : set_() {
On 2015/07/14 04:35:01, Benedikt Meurer wrote:
> Do we really need to use varargs here? You could apply the builder pattern
again
> instead.

Agreed, and even easier, since the purpose was simplifying authoring lists of
range IDs, and it turned out I just needed 0 (no conflicts), 1, or 2 conflicts,
I removed the entire builder for this scenario.

In contrast, there's still a benefit for the builder for LiveRange authoring,
because the data structures (pairs) are more complex.

https://codereview.chromium.org/1219063017/diff/140001/test/unittests/compile...
test/unittests/compiler/coalesced-live-ranges-unittest.cc:75: operator
LiveRangeIDs&() { return set_; }
On 2015/07/14 04:35:01, Benedikt Meurer wrote:
> Same here, there's no need for operator overloading.

Done.

[Mircea Trofin, 2015-07-15 05:18:46]

https://codereview.chromium.org/1219063017/diff/140001/src/compiler/coalesced...
File src/compiler/coalesced-live-ranges.h (right):

https://codereview.chromium.org/1219063017/diff/140001/src/compiler/coalesced...
src/compiler/coalesced-live-ranges.h:38: void VisitConflicts(const LiveRange*
range, ConstLiveRangePtrToBool visitor) {
On 2015/07/14 15:21:07, Mircea Trofin wrote:
> On 2015/07/14 05:13:04, Benedikt Meurer wrote:
> > Higher order functions which iterate over a data structure, and allow
> callbacks
> > to mutate the underlying data structure, are usually a bad idea, esp. in C++
> > (with STL). IMHO this is worse compared to the conflict_iterator.
> > 
> > What happened to the idea of simple loops? I thought we agreed on that as a
> > starting point.
> 
> I called this out in the code review description: the starting point suffered
> from code duplication and increased concept coupling. Both complicate (and
> increase cost of) maintenance and testing.
> 
> The starting point wasn't really simple loops either: both
> GetMaximumConflictingWeight and EvictAndRescheduleConflicts had to carefully
> traverse the set of allocated ranges, and in a very similar way. The
difference
> between the 2 was subtle and unnecessary (eviction had to skip over successive
> intervals of same range, finding max weight could do without that, but didn't
> need to). When looking into unit testing, the code duplication became clear.
> 
> I'm assuming your concern with potentially mutating visitors is about mutation
> invalidating the underlying iterator? I believe the implementation ensures
safe
> mutation, unless I'm missing something?

(to capture our discussion) We agreed to move to an iterator - based design,
without attempting to emulate the surface area of STL iterators. Instead, it'll
have explicit "Current" and "Next" and "HasNext" APIs rather than overloaded
operators a'la STL (->, ++, etc)

[Mircea Trofin, 2015-07-20 23:53:32]

Replaced the visitors with an iterator with a scenario-specific design, avoiding
STL-like APIs.

[Jarin, 2015-07-21 08:51:19]

https://codereview.chromium.org/1219063017/diff/180001/src/compiler/coalesced...
File src/compiler/coalesced-live-ranges.cc (right):

https://codereview.chromium.org/1219063017/diff/180001/src/compiler/coalesced...
src/compiler/coalesced-live-ranges.cc:66: break;
This continue-break gymnastics looks awkward.
How about 
if (pos_ != end) {
  DCHECK(QueryIntersectsAllocatedInterval());
  break;
}

Or possibly 

if (pos_ != end) {
  DCHECK(QueryIntersectsAllocatedInterval());
  return;
}

(Then you can unconditionally Invalidate after the loop.)

https://codereview.chromium.org/1219063017/diff/180001/src/compiler/coalesced...
src/compiler/coalesced-live-ranges.cc:96: storage_->erase({interval->start(),
interval->end(), nullptr});
Uniform initialization is banned in Chrome, apparently. Please equip
AllocationInterval with a constructor.

(See https://chromium-cpp.appspot.com. The reason for banning is incorrect
support in some versions of Visual Studio.)

https://codereview.chromium.org/1219063017/diff/180001/src/compiler/coalesced...
src/compiler/coalesced-live-ranges.cc:119: storage().insert({interval->start(),
interval->end(), range});
Same here, no uniform initialization.

https://codereview.chromium.org/1219063017/diff/180001/src/compiler/coalesced...
File src/compiler/coalesced-live-ranges.h (right):

https://codereview.chromium.org/1219063017/diff/180001/src/compiler/coalesced...
src/compiler/coalesced-live-ranges.h:48: LiveRange* ClearCurrentAndGetNext() {
return InternalGetNext(true); }
ClearCurrent seems ambiguous to me, it sounds like it is somehow invalidating
the current range.

How about EvictCurrentAndGetNext, then? (Or RemoveCurrentAndGetNext.)

https://codereview.chromium.org/1219063017/diff/180001/src/compiler/coalesced...
src/compiler/coalesced-live-ranges.h:100: IntervalStore* storage_;
Could we please move away from the 'storage_' name? It does not say at all what
the field is (every field is in essence storage). How about intervals_?

https://codereview.chromium.org/1219063017/diff/180001/src/compiler/coalesced...
src/compiler/coalesced-live-ranges.h:131: bool
TestOnlyVerifyAllocationsAreValid() const;
TestOnlyVerifyAllocationsAreValid -> VerifyAllocationsAreValidForTesting

The Chrome convention is to add the ForTesting suffix (and there are some rough
checks that aim to detect calls from production code to testing code (i.e.,
methods without the ForTesting suffix calling methods with the ForTesting
suffix).

https://codereview.chromium.org/1219063017/diff/180001/src/compiler/coalesced...
src/compiler/coalesced-live-ranges.h:136: IntervalStore& storage() { return
storage_; }
Again, could we rename storage -> intervals.

https://codereview.chromium.org/1219063017/diff/180001/test/unittests/compile...
File test/unittests/compiler/coalesced-live-ranges-unittest.cc (right):

https://codereview.chromium.org/1219063017/diff/180001/test/unittests/compile...
test/unittests/compiler/coalesced-live-ranges-unittest.cc:36: auto pair =
pairs_[i];
auto -> Interval

[Mircea Trofin, 2015-07-21 14:51:01]

https://codereview.chromium.org/1219063017/diff/180001/src/compiler/coalesced...
File src/compiler/coalesced-live-ranges.cc (right):

https://codereview.chromium.org/1219063017/diff/180001/src/compiler/coalesced...
src/compiler/coalesced-live-ranges.cc:66: break;
On 2015/07/21 08:51:18, jarin wrote:
> This continue-break gymnastics looks awkward.
> How about 
> if (pos_ != end) {
>   DCHECK(QueryIntersectsAllocatedInterval());
>   break;
> }
> 
> Or possibly 
> 
> if (pos_ != end) {
>   DCHECK(QueryIntersectsAllocatedInterval());
>   return;
> }
> 
> (Then you can unconditionally Invalidate after the loop.)

Done.

https://codereview.chromium.org/1219063017/diff/180001/src/compiler/coalesced...
src/compiler/coalesced-live-ranges.cc:96: storage_->erase({interval->start(),
interval->end(), nullptr});
On 2015/07/21 08:51:18, jarin wrote:
> Uniform initialization is banned in Chrome, apparently. Please equip
> AllocationInterval with a constructor.
> 
> (See https://chromium-cpp.appspot.com. The reason for banning is incorrect
> support in some versions of Visual Studio.)

Done.

https://codereview.chromium.org/1219063017/diff/180001/src/compiler/coalesced...
src/compiler/coalesced-live-ranges.cc:119: storage().insert({interval->start(),
interval->end(), range});
On 2015/07/21 08:51:18, jarin wrote:
> Same here, no uniform initialization.

Done.

https://codereview.chromium.org/1219063017/diff/180001/src/compiler/coalesced...
File src/compiler/coalesced-live-ranges.h (right):

https://codereview.chromium.org/1219063017/diff/180001/src/compiler/coalesced...
src/compiler/coalesced-live-ranges.h:48: LiveRange* ClearCurrentAndGetNext() {
return InternalGetNext(true); }
On 2015/07/21 08:51:18, jarin wrote:
> ClearCurrent seems ambiguous to me, it sounds like it is somehow invalidating
> the current range.
> 
> How about EvictCurrentAndGetNext, then? (Or RemoveCurrentAndGetNext.)

Done.

https://codereview.chromium.org/1219063017/diff/180001/src/compiler/coalesced...
src/compiler/coalesced-live-ranges.h:100: IntervalStore* storage_;
On 2015/07/21 08:51:18, jarin wrote:
> Could we please move away from the 'storage_' name? It does not say at all
what
> the field is (every field is in essence storage). How about intervals_?

Done.

https://codereview.chromium.org/1219063017/diff/180001/src/compiler/coalesced...
src/compiler/coalesced-live-ranges.h:131: bool
TestOnlyVerifyAllocationsAreValid() const;
On 2015/07/21 08:51:18, jarin wrote:
> TestOnlyVerifyAllocationsAreValid -> VerifyAllocationsAreValidForTesting
> 
> The Chrome convention is to add the ForTesting suffix (and there are some
rough
> checks that aim to detect calls from production code to testing code (i.e.,
> methods without the ForTesting suffix calling methods with the ForTesting
> suffix).

Ah, it was a suffix. Done.

https://codereview.chromium.org/1219063017/diff/180001/src/compiler/coalesced...
src/compiler/coalesced-live-ranges.h:136: IntervalStore& storage() { return
storage_; }
On 2015/07/21 08:51:18, jarin wrote:
> Again, could we rename storage -> intervals.

Done.

https://codereview.chromium.org/1219063017/diff/180001/test/unittests/compile...
File test/unittests/compiler/coalesced-live-ranges-unittest.cc (right):

https://codereview.chromium.org/1219063017/diff/180001/test/unittests/compile...
test/unittests/compiler/coalesced-live-ranges-unittest.cc:36: auto pair =
pairs_[i];
On 2015/07/21 08:51:18, jarin wrote:
> auto -> Interval

Done.

[Jarin, 2015-07-22 04:18:07]

lgtm

[Mircea Trofin, 2015-07-22 04:19:39]

The CQ bit was checked by mtrofin@chromium.org

[commit-bot: I haz the power, 2015-07-22 04:19:44]

CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/1219063017/200001

[commit-bot: I haz the power, 2015-07-22 04:50:21]

Committed patchset #5 (id:200001)

[commit-bot: I haz the power, 2015-07-22 04:50:34]

Patchset 5 (id:??) landed as
https://crrev.com/3e3608cdd5073965491db95b1fa085db506d468d
Cr-Commit-Position: refs/heads/master@{#29783}