Chromium Code Reviews
|
|
Chromium Code Reviews
Issue
1061923005:
Reland: Introducing the LLVM greedy register allocator. (Closed)
|
Created:
5 years, 8 months ago by Mircea Trofin Modified:
5 years, 8 months ago 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. |
DescriptionReland: Introducing the LLVM greedy register allocator.
This change aims to introduce the separation of the RegisterAllocator model, using the initial prototype for GreedyAllocator as proof of concept.
Summary:
- new flag, turbo-greedy-regalloc, enabling the new allocator. Default
false.
- initial, untested implementation for the GreedyAllocator.
BUG=
Committed: https://crrev.com/f3c04acad80e9346ec4e5435625aee8e3404fcdb
Cr-Commit-Position: refs/heads/master@{#28018}
Patch Set 1 : #
Total comments: 28
Patch Set 2 : #
Total comments: 20
Patch Set 3 : #
Total comments: 23
Patch Set 4 : #Patch Set 5 : Redo after refactoring #
Total comments: 10
Patch Set 6 : After 2nd rebase #Patch Set 7 : Small fix (DCHECK dissapearing in retail builds) #Patch Set 8 : win fix #Patch Set 9 : #
Total comments: 2
Patch Set 10 : #Patch Set 11 : #
Total comments: 7
Messages
Total messages: 50 (19 generated)
Patchset #1 (id:1) has been deleted
Patchset #2 (id:40001) has been deleted
Patchset #1 (id:20001) has been deleted
Patchset #1 (id:60001) has been deleted
Patchset #1 (id:80001) has been deleted
mtrofin@chromium.org changed reviewers: + dcarney@chromium.org, titzer@chromium.org
Fix incorrect use of DCHECK
Patchset #3 (id:140001) has been deleted
Patchset #2 (id:120001) has been deleted
Patchset #1 (id:100001) has been deleted
few small fixes
first round of comments: mostly to do with v8 style/peculiarities https://codereview.chromium.org/1061923005/diff/160001/src/compiler/register-... File src/compiler/register-allocator.cc (right): https://codereview.chromium.org/1061923005/diff/160001/src/compiler/register-... src/compiler/register-allocator.cc:13: const std::pair<int, int> this should go under the #define also, does this create a static initializer or does c++ inline this away? static initializers are not allowed. https://codereview.chromium.org/1061923005/diff/160001/src/compiler/register-... src/compiler/register-allocator.cc:1886: allocations_[i] = new RegisterAllocationInfo(local_zone()); this must be zone allocated - in fact pretty much everything inside a compilation must be https://codereview.chromium.org/1061923005/diff/160001/src/compiler/register-... src/compiler/register-allocator.cc:2293: while (pos) { while (pos != nullptr) nullptr comparisons tend to be explicit in v8 https://codereview.chromium.org/1061923005/diff/160001/src/compiler/register-... src/compiler/register-allocator.cc:2321: unsigned regId, LiveRange* range, ZoneSet<LiveRange*>& conflicting) { v8 would generally uses reg_id, not regId here https://codereview.chromium.org/1061923005/diff/160001/src/compiler/register-... src/compiler/register-allocator.cc:2333: if (conflicting.size()) return false; we tend to make compare with 0 explicit, should anyway be conflicting.empty(), or even conflicting->empty(), since non-const ref arguments are not allowed https://codereview.chromium.org/1061923005/diff/160001/src/compiler/register-... src/compiler/register-allocator.cc:2345: if (current->IsFixed()) need braces for conditions that are not on the same line https://codereview.chromium.org/1061923005/diff/160001/src/compiler/register-... src/compiler/register-allocator.cc:2354: for (unsigned candidateReg = 0; candidateReg < allocations_.size(); candidate_reg https://codereview.chromium.org/1061923005/diff/160001/src/compiler/register-... File src/compiler/register-allocator.h (right): https://codereview.chromium.org/1061923005/diff/160001/src/compiler/register-... src/compiler/register-allocator.h:696: class RegisterAllocationInfo { make ZoneObject https://codereview.chromium.org/1061923005/diff/160001/src/compiler/register-... src/compiler/register-allocator.h:698: explicit RegisterAllocationInfo(Zone* zone) : _storage(zone) {} this class doesn't need to be in the header. also it's probably got to much inline code. we've been trying to reduce that. in the implementation file it's obviously allowed though https://codereview.chromium.org/1061923005/diff/160001/src/compiler/register-... src/compiler/register-allocator.h:700: bool find(UseInterval* query, LiveRange*& result) { here and all over the place: functions in v8 start with capital letters except for trivial getters and setters https://codereview.chromium.org/1061923005/diff/160001/src/compiler/register-... src/compiler/register-allocator.h:753: ZoneSplayTree<Config> _storage; in v8 this must be called storage_ https://codereview.chromium.org/1061923005/diff/160001/src/compiler/register-... src/compiler/register-allocator.h:754: }; the chromium style guide was DISALLOW_COPY_AND_ASSIGN on all classed that you don't explicitly intend to be copied/assigned https://codereview.chromium.org/1061923005/diff/160001/src/compiler/register-... src/compiler/register-allocator.h:763: float CalculateMaxSpillWeight(ZoneSet<LiveRange*> ranges); you want ZoneSet<LiveRange*>* here to avoid epic levels of copying https://codereview.chromium.org/1061923005/diff/160001/src/compiler/register-... src/compiler/register-allocator.h:766: bool TryAllocate(LiveRange* current, ZoneSet<LiveRange*>& conflicting); ZoneSet<LiveRange*>* here as well, only const ref arguments allowed
Patchset #2 (id:180001) has been deleted
Incorporated feedback. Also added a ZonePriorityQueue. https://codereview.chromium.org/1061923005/diff/160001/src/compiler/register-... File src/compiler/register-allocator.cc (right): https://codereview.chromium.org/1061923005/diff/160001/src/compiler/register-... src/compiler/register-allocator.cc:13: const std::pair<int, int> On 2015/04/17 07:22:45, dcarney wrote: > this should go under the #define > also, does this create a static initializer or does c++ inline this away? > static initializers are not allowed. This is a constexpr, so it is evaluated at compile time. https://codereview.chromium.org/1061923005/diff/160001/src/compiler/register-... src/compiler/register-allocator.cc:1886: allocations_[i] = new RegisterAllocationInfo(local_zone()); On 2015/04/17 07:22:45, dcarney wrote: > this must be zone allocated - in fact pretty much everything inside a > compilation must be Done. https://codereview.chromium.org/1061923005/diff/160001/src/compiler/register-... src/compiler/register-allocator.cc:2293: while (pos) { On 2015/04/17 07:22:45, dcarney wrote: > while (pos != nullptr) > > nullptr comparisons tend to be explicit in v8 Done. https://codereview.chromium.org/1061923005/diff/160001/src/compiler/register-... src/compiler/register-allocator.cc:2321: unsigned regId, LiveRange* range, ZoneSet<LiveRange*>& conflicting) { On 2015/04/17 07:22:45, dcarney wrote: > v8 would generally uses reg_id, not regId here Done. https://codereview.chromium.org/1061923005/diff/160001/src/compiler/register-... src/compiler/register-allocator.cc:2333: if (conflicting.size()) return false; On 2015/04/17 07:22:45, dcarney wrote: > we tend to make compare with 0 explicit, should anyway be conflicting.empty(), > or even conflicting->empty(), since non-const ref arguments are not allowed Done. https://codereview.chromium.org/1061923005/diff/160001/src/compiler/register-... src/compiler/register-allocator.cc:2345: if (current->IsFixed()) On 2015/04/17 07:22:45, dcarney wrote: > need braces for conditions that are not on the same line Done. https://codereview.chromium.org/1061923005/diff/160001/src/compiler/register-... src/compiler/register-allocator.cc:2354: for (unsigned candidateReg = 0; candidateReg < allocations_.size(); On 2015/04/17 07:22:45, dcarney wrote: > candidate_reg Done. https://codereview.chromium.org/1061923005/diff/160001/src/compiler/register-... File src/compiler/register-allocator.h (right): https://codereview.chromium.org/1061923005/diff/160001/src/compiler/register-... src/compiler/register-allocator.h:696: class RegisterAllocationInfo { On 2015/04/17 07:22:45, dcarney wrote: > make ZoneObject Done. https://codereview.chromium.org/1061923005/diff/160001/src/compiler/register-... src/compiler/register-allocator.h:698: explicit RegisterAllocationInfo(Zone* zone) : _storage(zone) {} On 2015/04/17 07:22:46, dcarney wrote: > this class doesn't need to be in the header. > also it's probably got to much inline code. we've been trying to reduce that. in > the implementation file it's obviously allowed though Done. https://codereview.chromium.org/1061923005/diff/160001/src/compiler/register-... src/compiler/register-allocator.h:700: bool find(UseInterval* query, LiveRange*& result) { On 2015/04/17 07:22:46, dcarney wrote: > here and all over the place: functions in v8 start with capital letters except > for trivial getters and setters Done. https://codereview.chromium.org/1061923005/diff/160001/src/compiler/register-... src/compiler/register-allocator.h:753: ZoneSplayTree<Config> _storage; On 2015/04/17 07:22:45, dcarney wrote: > in v8 this must be called storage_ Done. https://codereview.chromium.org/1061923005/diff/160001/src/compiler/register-... src/compiler/register-allocator.h:754: }; On 2015/04/17 07:22:45, dcarney wrote: > the chromium style guide was DISALLOW_COPY_AND_ASSIGN on all classed that you > don't explicitly intend to be copied/assigned Done. https://codereview.chromium.org/1061923005/diff/160001/src/compiler/register-... src/compiler/register-allocator.h:763: float CalculateMaxSpillWeight(ZoneSet<LiveRange*> ranges); On 2015/04/17 07:22:46, dcarney wrote: > you want ZoneSet<LiveRange*>* here to avoid epic levels of copying Good catch, thanks! It was meant to be ZoneSet<LiveRange*>&, but given the guidance about refs only for constant parameters, moving to a pointer. https://codereview.chromium.org/1061923005/diff/160001/src/compiler/register-... src/compiler/register-allocator.h:766: bool TryAllocate(LiveRange* current, ZoneSet<LiveRange*>& conflicting); On 2015/04/17 07:22:45, dcarney wrote: > ZoneSet<LiveRange*>* here as well, only const ref arguments allowed Done.
you still have a bunch of places where you are comparing against zero/null without making it explicit. at least the following variables are still camel-cased in the header or the implementation file: regId, regNr, thisMax, maxConflicting, currentPair, allocInfo, useCount. one last style thing. GreedyAllocator and LinearScanAllocator fit v8 naming patterns better than RegisterAllocatorLinear and RegisterAllocatorGreedy now some more useful comments, which don't really have to be addressed in this cl: using the LiveRange class as it is is going to be difficult. there are a ton of assumptions about linear processing of ranges, and as such, no function that uses current_interval_ or last_processed_use_ can be used in its current form. for instance: NextUsePosition NextRegisterPosition NextUsePositionRegisterIsBeneficial PreviousUsePositionRegisterIsBeneficial FirstSearchIntervalForPosition AdvanceLastProcessedMarker are all invalid as well as the transitive closure of any thing that uses them. for instance: CanBeSpilled SplitAt i'm not sure what the best way to handle this will be. i think the current functions will need to remain intact to not regress the current allocator, which is already slow. https://codereview.chromium.org/1061923005/diff/200001/src/compiler/register-... File src/compiler/register-allocator.cc (right): https://codereview.chromium.org/1061923005/diff/200001/src/compiler/register-... src/compiler/register-allocator.cc:1919: auto pos = range->NextUsePositionRegisterIsBeneficial(next_pos); NextUsePositionRegisterIsBeneficial is not available to the Greedy allocator as requires in-order processing of intervals to work https://codereview.chromium.org/1061923005/diff/200001/src/compiler/register-... src/compiler/register-allocator.cc:1952: allocations_.resize(config()->kMaxGeneralRegisters); config()->num_general_registers() is the number of registers available to the current allocator kMaxGeneralRegisters is the max available across all platforms https://codereview.chromium.org/1061923005/diff/200001/src/compiler/register-... src/compiler/register-allocator.cc:1960: CHECK((allocations_[regNr]->Insert(current))); generally we ensure CHECK should be convertible to DCHECK and vice versa without affecting correctness bool inserted = allocations_[regNr]->Insert(current); CHECK(inserted); https://codereview.chromium.org/1061923005/diff/200001/src/compiler/register-... src/compiler/register-allocator.cc:1984: CHECK(AllocateBlockedRange(current, conflicting)); here and 2 lines above CHECK issue again https://codereview.chromium.org/1061923005/diff/200001/src/compiler/register-... src/compiler/register-allocator.cc:1988: for (unsigned i = 0; i < allocations_.size(); i++) { size_t here and in other places when iterating to a std container size() also, in all loops, use ++i, even for integers https://codereview.chromium.org/1061923005/diff/200001/src/compiler/register-... src/compiler/register-allocator.cc:1998: auto register_use = current->NextRegisterPosition(current->Start()); NextRegisterPosition is also unavailable to the greedy allocator https://codereview.chromium.org/1061923005/diff/200001/src/compiler/register-... src/compiler/register-allocator.cc:2347: DCHECK((unsigned)(range->assigned_register()) == reg_id); chromium style guide dictates that you must use static_cast<unsigned>() instead of c-style casts that being said, you probably want reg_id all over the place to be int, since that's how it's coming in also, we generally want DCHECK_EQ(expected_value, value) instead of DCHECK(expected_value == value) https://codereview.chromium.org/1061923005/diff/200001/src/compiler/register-... src/compiler/register-allocator.cc:2357: if (range->FirstHint() && range->FirstHint()->IsRegister()) need braces on multiline if https://codereview.chromium.org/1061923005/diff/200001/src/compiler/register-... src/compiler/register-allocator.cc:2377: float localMax = CalculateSpillWeight(r); max = std::max(max, CalculateSpillWeight(r) https://codereview.chromium.org/1061923005/diff/200001/src/compiler/register-... src/compiler/register-allocator.cc:2403: // good to insert comments in v8 typically start with a capital and end with a period and are generally complete sentences, but i'm really not sure if there are any rules about that
Patchset #3 (id:220001) has been deleted
Patchset #3 (id:230001) has been deleted
Thanks! I think I managed to squash all the remaining style violations now (fingers crossed!) About those LiveRange APIs - thanks for clarifying what was happening there! I was a bit surprised when I saw the stateful iterator implementation, but decided to punt worrying about that until after this initial CL. I agree with you, in the short term, it's safest to leave the current APIs as-is, and I'll add separately whatever I need for the backtracking allocator - perhaps as members to GreedyAllocator. Once I'm done with the port, I intend to look for opportunities for refactoring / cleanup. If we want both allocators to co-exist (I assume?), it'd help to have neutral shared concepts. How's this sound? https://codereview.chromium.org/1061923005/diff/200001/src/compiler/register-... File src/compiler/register-allocator.cc (right): https://codereview.chromium.org/1061923005/diff/200001/src/compiler/register-... src/compiler/register-allocator.cc:1919: auto pos = range->NextUsePositionRegisterIsBeneficial(next_pos); On 2015/04/18 19:01:33, dcarney wrote: > NextUsePositionRegisterIsBeneficial is not available to the Greedy allocator as > requires in-order processing of intervals to work Acknowledged. This will need a rewrite anyway. https://codereview.chromium.org/1061923005/diff/200001/src/compiler/register-... src/compiler/register-allocator.cc:1952: allocations_.resize(config()->kMaxGeneralRegisters); On 2015/04/18 19:01:32, dcarney wrote: > config()->num_general_registers() is the number of registers available to the > current allocator kMaxGeneralRegisters is the max available across all platforms Done. https://codereview.chromium.org/1061923005/diff/200001/src/compiler/register-... src/compiler/register-allocator.cc:1960: CHECK((allocations_[regNr]->Insert(current))); On 2015/04/18 19:01:33, dcarney wrote: > generally we ensure CHECK should be convertible to DCHECK and vice versa without > affecting correctness > > bool inserted = allocations_[regNr]->Insert(current); > CHECK(inserted); Done. https://codereview.chromium.org/1061923005/diff/200001/src/compiler/register-... src/compiler/register-allocator.cc:1984: CHECK(AllocateBlockedRange(current, conflicting)); On 2015/04/18 19:01:33, dcarney wrote: > here and 2 lines above CHECK issue again Done. https://codereview.chromium.org/1061923005/diff/200001/src/compiler/register-... src/compiler/register-allocator.cc:1988: for (unsigned i = 0; i < allocations_.size(); i++) { On 2015/04/18 19:01:33, dcarney wrote: > size_t here and in other places when iterating to a std container size() > also, in all loops, use ++i, even for integers Done. https://codereview.chromium.org/1061923005/diff/200001/src/compiler/register-... src/compiler/register-allocator.cc:1998: auto register_use = current->NextRegisterPosition(current->Start()); On 2015/04/18 19:01:33, dcarney wrote: > NextRegisterPosition is also unavailable to the greedy allocator Acknowledged. https://codereview.chromium.org/1061923005/diff/200001/src/compiler/register-... src/compiler/register-allocator.cc:2347: DCHECK((unsigned)(range->assigned_register()) == reg_id); On 2015/04/18 19:01:33, dcarney wrote: > chromium style guide dictates that you must use static_cast<unsigned>() instead > of c-style casts > that being said, you probably want reg_id all over the place to be int, since > that's how it's coming in > > also, we generally want DCHECK_EQ(expected_value, value) instead of > DCHECK(expected_value == value) Done. https://codereview.chromium.org/1061923005/diff/200001/src/compiler/register-... src/compiler/register-allocator.cc:2357: if (range->FirstHint() && range->FirstHint()->IsRegister()) On 2015/04/18 19:01:33, dcarney wrote: > need braces on multiline if Done. https://codereview.chromium.org/1061923005/diff/200001/src/compiler/register-... src/compiler/register-allocator.cc:2377: float localMax = CalculateSpillWeight(r); On 2015/04/18 19:01:33, dcarney wrote: > max = std::max(max, CalculateSpillWeight(r) Done. https://codereview.chromium.org/1061923005/diff/200001/src/compiler/register-... src/compiler/register-allocator.cc:2403: // good to insert On 2015/04/18 19:01:33, dcarney wrote: > comments in v8 typically start with a capital and end with a period and are > generally complete sentences, but i'm really not sure if there are any rules > about that Done.
Okay, style-wise you're looking good. I don't want to comment on the implementation of GreedyAllocator at all since it'll completely change I assume. I left some comments on RegisterAllocationInfo since that seemed more likely to be stable. Maybe we could chat sometime this week about ways to make the split cleaner/easier for you to work with (after landing this cl)? https://codereview.chromium.org/1061923005/diff/250001/src/compiler/register-... File src/compiler/register-allocator.cc (right): https://codereview.chromium.org/1061923005/diff/250001/src/compiler/register-... src/compiler/register-allocator.cc:20: class RegisterAllocationInfo : public ZoneObject { this is a pretty generic name, to be avoided if possible. i don't have a suggestion really, but it's something to think about changing if you come up with one https://codereview.chromium.org/1061923005/diff/250001/src/compiler/register-... src/compiler/register-allocator.cc:24: bool Find(UseInterval* query, LiveRange** result) { what about just returning a live range that could be null? might be simpler, but i'm sort of indifferent https://codereview.chromium.org/1061923005/diff/250001/src/compiler/register-... src/compiler/register-allocator.cc:36: if (!Insert(interval, range)) return false; if i'm reading the rest of this cl correctly, this insert has to succeed or something has gone terribly wrong. just DCHECK that insertion succeeded and return void for the function https://codereview.chromium.org/1061923005/diff/250001/src/compiler/register-... src/compiler/register-allocator.cc:42: bool Remove(UseInterval* key) { return storage_.Remove(GetKey(key)); } this should probably be private since i can't imagine individual intervals will be removable https://codereview.chromium.org/1061923005/diff/250001/src/compiler/register-... src/compiler/register-allocator.cc:48: ret |= Remove(segment); again, the intervals must all be in there somewhere, just DCHECK that removal succeeded are return void https://codereview.chromium.org/1061923005/diff/250001/src/compiler/register-... src/compiler/register-allocator.cc:70: if (!interval) return std::make_pair(0, 0); interval != nullptr https://codereview.chromium.org/1061923005/diff/250001/src/compiler/register-... src/compiler/register-allocator.cc:75: bool ret = storage_.Insert(GetKey(interval), &locator); here you should be able to DCHEK ret as well, no? https://codereview.chromium.org/1061923005/diff/250001/src/compiler/register-... src/compiler/register-allocator.cc:1896: DCHECK(size); size != 0 https://codereview.chromium.org/1061923005/diff/250001/src/compiler/register-... src/compiler/register-allocator.cc:1902: if (!range || range->IsEmpty()) return; range == nullptr https://codereview.chromium.org/1061923005/diff/250001/src/compiler/register-... src/compiler/register-allocator.cc:1953: int reg_count = mode == GENERAL_REGISTERS ? config()->num_general_registers() maybe you want to use num_registers_ like in the linearscan case, and just have 1 virtual function called AllocateRegisters()? not sure that's actually necessary, but the logic is already there https://codereview.chromium.org/1061923005/diff/250001/src/compiler/register-... src/compiler/register-allocator.cc:1961: for (auto* current : fixed_live_ranges()) { i think if you just switch between fixed_live_ranges() and fixed_double_live_ranges() here, support for double registers is complete
> I agree with you, in the short term, it's safest to leave the current APIs > as-is, and I'll add separately whatever I need for the backtracking allocator - > perhaps as members to GreedyAllocator. > > Once I'm done with the port, I intend to look for opportunities for refactoring > / cleanup. If we want both allocators to co-exist (I assume?), it'd help to have > neutral shared concepts. this plan is to get rid of the linear scan allocator and merge the greedy one back into the base class. even so, we'll have to have a better way to split up the code in the meantime
https://codereview.chromium.org/1061923005/diff/250001/src/compiler/register-... File src/compiler/register-allocator.cc (right): https://codereview.chromium.org/1061923005/diff/250001/src/compiler/register-... src/compiler/register-allocator.cc:20: class RegisterAllocationInfo : public ZoneObject { On 2015/04/19 12:21:01, dcarney wrote: > this is a pretty generic name, to be avoided if possible. i don't have a > suggestion really, but it's something to think about changing if you come up > with one I share the sentiment :) I'll try and find a better name, here are some suggestions (so I do the refactoring once): RegisterLiveRanges (my pick) RegisterLiveRangeAllocations same as above but with "Physical" in front - unless we say "Register" means physical, unless "Virtual" is used in front? I feel that's the convention used in this codebase, isn't it? https://codereview.chromium.org/1061923005/diff/250001/src/compiler/register-... src/compiler/register-allocator.cc:24: bool Find(UseInterval* query, LiveRange** result) { On 2015/04/19 12:21:01, dcarney wrote: > what about just returning a live range that could be null? might be simpler, but > i'm sort of indifferent I agree - changed it. https://codereview.chromium.org/1061923005/diff/250001/src/compiler/register-... src/compiler/register-allocator.cc:36: if (!Insert(interval, range)) return false; On 2015/04/19 12:21:01, dcarney wrote: > if i'm reading the rest of this cl correctly, this insert has to succeed or > something has gone terribly wrong. just DCHECK that insertion succeeded and > return void for the function SplayTree.Insert returns false if we already inserted that value. I'll leave it as bool-returning but add a TODO to cleanup if it turns out I don't need this piece of information. https://codereview.chromium.org/1061923005/diff/250001/src/compiler/register-... src/compiler/register-allocator.cc:42: bool Remove(UseInterval* key) { return storage_.Remove(GetKey(key)); } On 2015/04/19 12:21:01, dcarney wrote: > this should probably be private since i can't imagine individual intervals will > be removable Done. https://codereview.chromium.org/1061923005/diff/250001/src/compiler/register-... src/compiler/register-allocator.cc:48: ret |= Remove(segment); On 2015/04/19 12:21:01, dcarney wrote: > again, the intervals must all be in there somewhere, just DCHECK that removal > succeeded are return void I added that logic in the uses of the API, to avoid coupling too much with those uses. "Evict" is where trying to Remove something that wasn't added constitutes a bug. https://codereview.chromium.org/1061923005/diff/250001/src/compiler/register-... src/compiler/register-allocator.cc:75: bool ret = storage_.Insert(GetKey(interval), &locator); On 2015/04/19 12:21:01, dcarney wrote: > here you should be able to DCHEK ret as well, no? No, it just means we'd already inserted that. This API doesn't know if that's an error. https://codereview.chromium.org/1061923005/diff/250001/src/compiler/register-... src/compiler/register-allocator.cc:1896: DCHECK(size); On 2015/04/19 12:21:01, dcarney wrote: > size != 0 not DCHECK_NE(0, size)? I went with this, in the spirit of DCHECK_EQ - but let me know https://codereview.chromium.org/1061923005/diff/250001/src/compiler/register-... src/compiler/register-allocator.cc:1902: if (!range || range->IsEmpty()) return; On 2015/04/19 12:21:01, dcarney wrote: > range == nullptr Done. https://codereview.chromium.org/1061923005/diff/250001/src/compiler/register-... src/compiler/register-allocator.cc:1953: int reg_count = mode == GENERAL_REGISTERS ? config()->num_general_registers() On 2015/04/19 12:21:01, dcarney wrote: > maybe you want to use num_registers_ like in the linearscan case, and just have > 1 virtual function called AllocateRegisters()? not sure that's actually > necessary, but the logic is already there I am a bit uneasy with the existing pattern, actually. Type fields seem to me more appropriate to state necessary across many uses. Perhaps that is the case with the Linear one, although even there the mode_ and num_registers_ fields seem used only for the allocation scenario, not the live range calculations, for example. I would consider doing mode_ and num_registers_ as fields if we had 2 instances of allocators, one for general and one for double registers, but that would make even more sense if the different responsibilities currently co-located within the RegisterAllocator - pretty much each individual phase - were factored out. Not sure what the rationale for the current design is, though, and this design issue feels mostly orthogonal at this point. So I would punt this one until the new allocator is alive and well. https://codereview.chromium.org/1061923005/diff/250001/src/compiler/register-... src/compiler/register-allocator.cc:1961: for (auto* current : fixed_live_ranges()) { On 2015/04/19 12:21:01, dcarney wrote: > i think if you just switch between fixed_live_ranges() and > fixed_double_live_ranges() here, support for double registers is complete Done - something along those lines.
https://codereview.chromium.org/1061923005/diff/250001/src/compiler/register-... File src/compiler/register-allocator.cc (right): https://codereview.chromium.org/1061923005/diff/250001/src/compiler/register-... src/compiler/register-allocator.cc:1896: DCHECK(size); On 2015/04/19 16:13:38, Mircea Trofin wrote: > On 2015/04/19 12:21:01, dcarney wrote: > > size != 0 > > not DCHECK_NE(0, size)? I went with this, in the spirit of DCHECK_EQ - but let > me know yeah, DCHECK_NE is better if it compiles. for size_t there's an issue in our DCHECK implementation that doesn't compile. when i saw size i assumed there would be trouble https://codereview.chromium.org/1061923005/diff/250001/src/compiler/register-... src/compiler/register-allocator.cc:1953: int reg_count = mode == GENERAL_REGISTERS ? config()->num_general_registers() > I would consider doing mode_ and num_registers_ as fields if we had 2 instances > of allocators, one for general and one for double registers, but that would make > even more sense if the different responsibilities currently co-located within > the RegisterAllocator - pretty much each individual phase - were factored out. > Not sure what the rationale for the current design is, though, and this design > issue feels mostly orthogonal at this point. So I would punt this one until the > new allocator is alive and well. the current design splits the allocation of double and general ranges because linear scan has non linear behaviour in the size of the active and inactive lists. running allocate twice to potentially cut down those sizes on each individual execution makes sense and it's okay to do so since the two sets of ranges are completely disjoint. the rest of the register allocation phases don't have this property, which is why mode_ and num_registers_ are unused/invalid elsewhere
quick update i'm currently splitting the register allocator into little pieces, which will make your cl smaller and more focused. it'll require some rebasing on your part... will update when everything's in place
okay, phase one of the refactor is here and will land soon: https://codereview.chromium.org/1094063002/ this is going to change some things for you: I was forced, due to no one coming up with a better name, to introduce a RegisterAllocationData class, which means there is no way you can have a RegisterAllocationInfo class how about CoalescedLiveRanges? that's what it currently is, and if you go with that name, that's what it'll stay... I reordered stuff in the impl file by class, so your whole cl needs to go in one spot now i talked with the team, and no one seemed to want a virtual allocator base class, and there's anyway no need anymore, so you're need to devirtualize i'm still not sure what to do about all the splitting functions currently in LinearScanAllocator. the GreedyAllocator can't use them in their current form, so they should stay in LinearAllocator until we can figure out what to do with them
Updated after the refactoring. Consolidated some common functionality into helper utility functions (see GetRegisterCount and GetFixedRegisters). Moved (opportunistically) stateless, live range-splitting APIs to RegisterAllocationData, since they need code-wide context, but are independent of allocation scheme. The rest of the GreedyAllocator code is unchanged right now (so has the same problems noted before).
On 2015/04/20 18:31:44, Mircea Trofin wrote: > Updated after the refactoring. > > Consolidated some common functionality into helper utility functions (see > GetRegisterCount and GetFixedRegisters). > > Moved (opportunistically) stateless, live range-splitting APIs to > RegisterAllocationData, since they need code-wide context, but are independent > of allocation scheme. > > The rest of the GreedyAllocator code is unchanged right now (so has the same > problems noted before). looking good. i'll do the transition to stateless live ranges tomorrow, which will incorporate some of the stuff in this cl, and then we'll be ready to land
okay, please refactor one more time after https://codereview.chromium.org/1100713003/ lands. you'll just need to extend RegisterAllocator the only change i'd like is that the code comes in order of appearance in the header, as it's all currently ordered by phases, meaning both CoallescedLiveRanges and GreedyAllocator should appear between LinearScanAllocator and OperandAssigner. the constructors should come first for each class, but other than that it's irrelevant
dcarney@chromium.org changed reviewers: + jarin@chromium.org
jvoung@chromium.org changed reviewers: + jvoung@chromium.org
Throwing out some random nits from the CC list. https://codereview.chromium.org/1061923005/diff/290001/src/compiler/register-... File src/compiler/register-allocator.cc (right): https://codereview.chromium.org/1061923005/diff/290001/src/compiler/register-... src/compiler/register-allocator.cc:2642: // GetLiveRangeSize is DCHECK-ed to not be 0 GetLiveRangeSize can be 0 if range->first_interval() == nullptr, but maybe it's not possible at this point. https://codereview.chromium.org/1061923005/diff/290001/src/compiler/register-... src/compiler/register-allocator.cc:2732: // Nothing to spill. Just put it to unhandled as whole. nit: This comment seems to come from the LinearScan version, but for GreedyAllocator there isn't an "unhandled"? Can this be phrased differently? https://codereview.chromium.org/1061923005/diff/290001/src/compiler/register-... src/compiler/register-allocator.cc:2809: DCHECK(conflicting.size()); Is there an !empty() method to check instead of size()? https://codereview.chromium.org/1061923005/diff/290001/src/compiler/register-... src/compiler/register-allocator.cc:2820: DCHECK_EQ(0, conflicting.size()); conflicting.empty() ? https://codereview.chromium.org/1061923005/diff/290001/src/compiler/register-... File src/compiler/register-allocator.h (right): https://codereview.chromium.org/1061923005/diff/290001/src/compiler/register-... src/compiler/register-allocator.h:710: I don't know if v8 style would say to include a comment or some sort of link to describe where the algorithm comes from.
Incorporated Jan's feedback. https://codereview.chromium.org/1061923005/diff/290001/src/compiler/register-... File src/compiler/register-allocator.cc (right): https://codereview.chromium.org/1061923005/diff/290001/src/compiler/register-... src/compiler/register-allocator.cc:2642: // GetLiveRangeSize is DCHECK-ed to not be 0 On 2015/04/21 23:34:06, jvoung wrote: > GetLiveRangeSize can be 0 if range->first_interval() == nullptr, but maybe it's > not possible at this point. Thanks! Moved the check here. https://codereview.chromium.org/1061923005/diff/290001/src/compiler/register-... src/compiler/register-allocator.cc:2732: // Nothing to spill. Just put it to unhandled as whole. On 2015/04/21 23:34:06, jvoung wrote: > nit: This comment seems to come from the LinearScan version, but for > GreedyAllocator there isn't an "unhandled"? Can this be phrased differently? Most likely this copy of the API will be deleted once we make them stateless. But your suggestion is correct, we'd need to come up with comments that avoid algorithm specifics, at this level. https://codereview.chromium.org/1061923005/diff/290001/src/compiler/register-... src/compiler/register-allocator.cc:2809: DCHECK(conflicting.size()); On 2015/04/21 23:34:06, jvoung wrote: > Is there an !empty() method to check instead of size()? Done. https://codereview.chromium.org/1061923005/diff/290001/src/compiler/register-... src/compiler/register-allocator.cc:2820: DCHECK_EQ(0, conflicting.size()); On 2015/04/21 23:34:06, jvoung wrote: > conflicting.empty() ? Done. https://codereview.chromium.org/1061923005/diff/290001/src/compiler/register-... File src/compiler/register-allocator.h (right): https://codereview.chromium.org/1061923005/diff/290001/src/compiler/register-... src/compiler/register-allocator.h:710: On 2015/04/21 23:34:06, jvoung wrote: > I don't know if v8 style would say to include a comment or some sort of link to > describe where the algorithm comes from. Done.
lgtm, after the below comments are done you should be able to check the cq box now that you've gotten my lgtm https://codereview.chromium.org/1061923005/diff/370001/src/compiler/register-... File src/compiler/register-allocator.cc (right): https://codereview.chromium.org/1061923005/diff/370001/src/compiler/register-... src/compiler/register-allocator.cc:20: class CoallescedLiveRanges : public ZoneObject { please move this class below the last LinearScanAllocator function https://codereview.chromium.org/1061923005/diff/370001/src/compiler/register-... src/compiler/register-allocator.cc:2610: GreedyAllocator::GreedyAllocator(RegisterAllocationData* data, please move all functions for this class above the OperandAssigner functions
Patchset #10 (id:390001) has been deleted
The CQ bit was checked by mtrofin@chromium.org
The patchset sent to the CQ was uploaded after l-g-t-m from dcarney@chromium.org Link to the patchset: https://codereview.chromium.org/1061923005/#ps410001 (title: " ")
CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/patch-status/1061923005/410001
Done - sorry about the ordering, I interpreted your previous feedback as referring to ordering only in the header files. I selected the CQ option, however it may not work because of permissions (lack of, on my side). What is the usual procedure in such cases, could someone commit it for me? Thanks!
Message was sent while issue was closed.
Committed patchset #10 (id:410001)
Message was sent while issue was closed.
Patchset 10 (id:??) landed as https://crrev.com/ec542dea6b6a0cb82d1578a389569d019a59121d Cr-Commit-Position: refs/heads/master@{#28015}
Message was sent while issue was closed.
A revert of this CL (patchset #10 id:410001) has been created in https://codereview.chromium.org/1080953006/ by arv@chromium.org. The reason for reverting is: Breaks Static Initializers test. http://build.chromium.org/p/client.v8/builders/V8%20Linux64/builds/3210/steps....
The CQ bit was checked by mtrofin@chromium.org
The patchset sent to the CQ was uploaded after l-g-t-m from dcarney@chromium.org Link to the patchset: https://codereview.chromium.org/1061923005/#ps430001 (title: " ")
CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/patch-status/1061923005/430001
Static initializer fix
Message was sent while issue was closed.
Committed patchset #11 (id:430001)
Message was sent while issue was closed.
Patchset 11 (id:??) landed as https://crrev.com/f3c04acad80e9346ec4e5435625aee8e3404fcdb Cr-Commit-Position: refs/heads/master@{#28018}
Message was sent while issue was closed.
adding a few comments i left out before because i wanted to get this landed. Please address them in a followup cl at some point. no hurry https://codereview.chromium.org/1061923005/diff/430001/src/compiler/register-... File src/compiler/register-allocator.cc (right): https://codereview.chromium.org/1061923005/diff/430001/src/compiler/register-... src/compiler/register-allocator.cc:2195: two spaces here, and between pretty much everything except in class definitions https://codereview.chromium.org/1061923005/diff/430001/src/compiler/register-... src/compiler/register-allocator.cc:2282: two spaces https://codereview.chromium.org/1061923005/diff/430001/src/compiler/register-... src/compiler/register-allocator.cc:2308: two spaces https://codereview.chromium.org/1061923005/diff/430001/src/compiler/register-... src/compiler/register-allocator.cc:2347: // LinearScanAllocator::AllocateRegisters remove this comment. we want as little consolidation as possible between the allocators from now on i think, since they should have very little in common https://codereview.chromium.org/1061923005/diff/430001/src/compiler/register-... src/compiler/register-allocator.cc:2391: allocations_[i] = new (zone) CoallescedLiveRanges(zone); these should go in the local zone, which you have on GreedyAllocator construction. you can get it from allocations.get_allocator().zone() https://codereview.chromium.org/1061923005/diff/430001/src/compiler/register-... src/compiler/register-allocator.cc:2430: BitVector* assigned_registers = new (zone) BitVector(num_registers(), zone); this is actually a bug, the assigned_registers should be in the code_zone(), but actually they already are there on RegisterAllocationData it's wrong to reset them on the frame below since they acquire some data during constraintbuilding, just mark the correct bits in the below loop, something like if (mode == DOUBLE_REGISTERS) { data()->assigned_double_registers()->Add(i); } else { data()->assigned_registers()->Add(i); } https://codereview.chromium.org/1061923005/diff/430001/src/compiler/register-... src/compiler/register-allocator.cc:2436: data()->frame()->SetAllocatedRegisters(assigned_registers); remove |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
