Chromium Code Reviews
|
|
Chromium Code Reviews|
Created:
5 years, 5 months ago by Mircea Trofin Modified:
5 years, 5 months ago Reviewers:
Benedikt Meurer, Jarin CC:
v8-dev, Jim Stichnoth, jvoung (off chromium) Base URL:
https://chromium.googlesource.com/v8/v8.git@master Target Ref:
refs/pending/heads/master Project:
v8 Visibility:
Public. |
DescriptionUnit 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}
Patch Set 1 : #
Total comments: 4
Patch Set 2 : Incorporated feedback. #
Total comments: 7
Patch Set 3 : #Patch Set 4 : #
Total comments: 16
Patch Set 5 : #
Created: 5 years, 5 months ago
Messages
Total messages: 23 (8 generated)
Patchset #5 (id:80001) has been deleted
Patchset #5 (id:100001) has been deleted
Patchset #4 (id:60001) has been deleted
Patchset #1 (id:1) has been deleted
Patchset #1 (id:20001) has been deleted
Patchset #1 (id:40001) has been deleted
mtrofin@chromium.org changed reviewers: + bmeurer@chromium.org, jarin@chromium.org
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?
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.
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.
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.
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?
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.
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)
Replaced the visitors with an iterator with a scenario-specific design, avoiding STL-like APIs.
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
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.
lgtm
The CQ bit was checked by mtrofin@chromium.org
CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/patch-status/1219063017/200001
Message was sent while issue was closed.
Committed patchset #5 (id:200001)
Message was sent while issue was closed.
Patchset 5 (id:??) landed as https://crrev.com/3e3608cdd5073965491db95b1fa085db506d468d Cr-Commit-Position: refs/heads/master@{#29783} |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
