Chromium Code Reviews
|
|
Chromium Code Reviews
Issue
11415173:
Array bounds check elimination. (Closed)
|
Created:
8 years ago by Massi Modified:
5 years ago Reviewers:
Jakob Kummerow CC:
v8-dev Visibility:
Public. |
DescriptionArray bounds check elimination.
BUG=
Patch Set 1 #Patch Set 2 : Refactoring (and fixing refactoring issues). #
Total comments: 75
Messages
Total messages: 3 (1 generated)
High-level comments: 1) Don't do changes of this size. Seriously. Begin small, with a proof of concept, handle one basic case. Get feedback on it, ideally by full review and commit, but at least by detailed offline discussion. *After* that, expand on it, make it more clever, handle more cases. Work in small chunks (100-200 lines per CL is good, if you have any choice at all). Coming out of your cave with a 1000-line handles-everything-and-prepares-five-future-features monster adds unnecessary pain for both you and your reviewer. What if I don't like the cost/benefit ratio of the approach at all? Then weeks of work will go to waste. 2) As discussed offline at length, I think the long-term solution we want is (some form of) SSI, integrated deeply in the overall Hydrogen infrastructure, rather than a self-contained graph walking algorithm bolted onto an SSA graph. That should help us avoid this entangled mess of maps, pointers, pointers to pointers, intertwined lists over the same elements and so on. 3) Read http://google-styleguide.googlecode.com/svn/trunk/cppguide.xml. All of it. Low-level comments below. You needn't bother addressing them if you're following another approach now anyway, but it wouldn't hurt to take a look at how the code itself can be improved regardless of whether the high-level algorithm is changed or not. https://chromiumcodereview.appspot.com/11415173/diff/2001/src/hydrogen.cc File src/hydrogen.cc (right): https://chromiumcodereview.appspot.com/11415173/diff/2001/src/hydrogen.cc#new... src/hydrogen.cc:3692: HValue* Base() { return base_; } nit: lower-case names for simple accessors. https://chromiumcodereview.appspot.com/11415173/diff/2001/src/hydrogen.cc#new... src/hydrogen.cc:3693: HBoundsCheck* Check() { return check_; } nit: lower-case names for simple accessors. https://chromiumcodereview.appspot.com/11415173/diff/2001/src/hydrogen.cc#new... src/hydrogen.cc:3694: int Offset() { return offset_; } nit: lower-case names for simple accessors. https://chromiumcodereview.appspot.com/11415173/diff/2001/src/hydrogen.cc#new... src/hydrogen.cc:3698: HConstant* new_constant = new(zone()) nit: please break the line after '=', and indent the second line by 4 spaces. https://chromiumcodereview.appspot.com/11415173/diff/2001/src/hydrogen.cc#new... src/hydrogen.cc:3710: Check()->SetOperandAt(0, added_add_); I'd prefer introducing a method HBoundsCheck::SetIndex(HValue* index) { SetOperandAt(0, index); } for this, to keep the internal ordering of operands local to the HBoundsCheck class. https://chromiumcodereview.appspot.com/11415173/diff/2001/src/hydrogen.cc#new... src/hydrogen.cc:3715: void RemoveNullAdd() { Why do we have to do this as an additional step? Can't this be folded into ChangeOffset? Probably something like: if (new_offset == 0) { if (added_add_ != NULL) { DeleteAndReplaceWith(...) added_add_ = NULL; } return; } Or am I overlooking some reason why that can't work? https://chromiumcodereview.appspot.com/11415173/diff/2001/src/hydrogen.cc#new... src/hydrogen.cc:3724: BoundsCheckManipulationData(HValue* base, HBoundsCheck* check, int offset) : nit: ':' goes on the next line, with 4-space indentation. Also, the constructor should be the first thing in the "public:" section. https://chromiumcodereview.appspot.com/11415173/diff/2001/src/hydrogen.cc#new... src/hydrogen.cc:3735: Zone* zone() { return Check()->block()->zone(); } nit: methods before data members https://chromiumcodereview.appspot.com/11415173/diff/2001/src/hydrogen.cc#new... src/hydrogen.cc:3760: explicit BoundsCheckValueInfoTable(Zone* zone) nit: the constructor should be the first thing in the "public:" section. https://chromiumcodereview.appspot.com/11415173/diff/2001/src/hydrogen.cc#new... src/hydrogen.cc:3764: ZoneAllocationPolicy(zone)){ } nit: space before '{' https://chromiumcodereview.appspot.com/11415173/diff/2001/src/hydrogen.cc#new... src/hydrogen.cc:3765: private: nit: empty line before "private:" (doesn't presubmit.py complain about this?) https://chromiumcodereview.appspot.com/11415173/diff/2001/src/hydrogen.cc#new... src/hydrogen.cc:3773: NE, Feel free to put all values onto the same line (I don't care either way). https://chromiumcodereview.appspot.com/11415173/diff/2001/src/hydrogen.cc#new... src/hydrogen.cc:3797: BoundsCheckRemovalBlockContext( again, constructor comes first https://chromiumcodereview.appspot.com/11415173/diff/2001/src/hydrogen.cc#new... src/hydrogen.cc:3800: : table_(previous != NULL ? previous->table() : proper indentation please: : table_(previous != NULL ? previous->table() : new(block->graph()->zone()) BoundsCheckValueInfoTable(block->graph()->zone())), block_(block), bb_data_list_(NULL), previous_(previous) {} Consider moving the initialization of table_ into the constructor's body instead: if (previous_ == NULL) { Zone* zone = block_->graph()->zone(); table_ = new(zone) BoundsCheckValueInfoTable(zone); } else { table_ = previous_->table(); } https://chromiumcodereview.appspot.com/11415173/diff/2001/src/hydrogen.cc#new... src/hydrogen.cc:3814: // Each fact has the form "value relation constraint", where value and suggestion: // Each fact has the form (value, relation, constraint) with types // (HValue*, ValueInfoRelation, HValue*). https://chromiumcodereview.appspot.com/11415173/diff/2001/src/hydrogen.cc#new... src/hydrogen.cc:3819: HValue* Value() { return value_; } nit: lower-case names for simple accessors. https://chromiumcodereview.appspot.com/11415173/diff/2001/src/hydrogen.cc#new... src/hydrogen.cc:3820: ValueInfoRelation Relation() { return relation_; } nit: lower-case names for simple accessors. https://chromiumcodereview.appspot.com/11415173/diff/2001/src/hydrogen.cc#new... src/hydrogen.cc:3821: HValue* Constraint() { return constraint_; } nit: lower-case names for simple accessors. https://chromiumcodereview.appspot.com/11415173/diff/2001/src/hydrogen.cc#new... src/hydrogen.cc:3822: // True if Value() will "cover" every single integer value in the range s/"cover"/take/ https://chromiumcodereview.appspot.com/11415173/diff/2001/src/hydrogen.cc#new... src/hydrogen.cc:3826: bool IsIncremental() { return is_incremental_; } nit: lower-case names for simple accessors. https://chromiumcodereview.appspot.com/11415173/diff/2001/src/hydrogen.cc#new... src/hydrogen.cc:3831: return c->DoubleValue() == 0.0; This won't work for non-number constants. Use "return c->HasDoubleValue() && c->DoubleValue() == 0.0;" instead. Also, why *double* value? Aren't you more interested in integers? https://chromiumcodereview.appspot.com/11415173/diff/2001/src/hydrogen.cc#new... src/hydrogen.cc:3835: // A HBoundsCheck on the same index; it is equivalent to having... ...? https://chromiumcodereview.appspot.com/11415173/diff/2001/src/hydrogen.cc#new... src/hydrogen.cc:3836: HBoundsCheck* BoundsCheck() { return bounds_check_; } nit: lower-case names for simple accessors. https://chromiumcodereview.appspot.com/11415173/diff/2001/src/hydrogen.cc#new... src/hydrogen.cc:3838: // The following properties are all helpers for CoverCheckWithBase. If they're helpers for another member, why are they public? https://chromiumcodereview.appspot.com/11415173/diff/2001/src/hydrogen.cc#new... src/hydrogen.cc:3846: int CheckOffset() { return check_offset_; } nit: lower-case names for simple accessors. https://chromiumcodereview.appspot.com/11415173/diff/2001/src/hydrogen.cc#new... src/hydrogen.cc:3848: BoundsCheckManipulationData* LowerCheck() { return lower_check_; } nit: lower-case names for simple accessors. https://chromiumcodereview.appspot.com/11415173/diff/2001/src/hydrogen.cc#new... src/hydrogen.cc:3850: BoundsCheckManipulationData* UpperCheck() { return upper_check_; } nit: lower-case names for simple accessors. https://chromiumcodereview.appspot.com/11415173/diff/2001/src/hydrogen.cc#new... src/hydrogen.cc:3852: bool HasNoBaseHandledCheck() { return lower_check_ == NULL; } What's a BaseHandledCheck? Why not just "HasNoCheck"? https://chromiumcodereview.appspot.com/11415173/diff/2001/src/hydrogen.cc#new... src/hydrogen.cc:3860: HBasicBlock* BasicBlock() const { return basic_block_; } nit: lower-case names for simple accessors. https://chromiumcodereview.appspot.com/11415173/diff/2001/src/hydrogen.cc#new... src/hydrogen.cc:3862: BoundsCheckValueInfo* NextForValue() { return next_for_value_; } nit: lower-case names for simple accessors. https://chromiumcodereview.appspot.com/11415173/diff/2001/src/hydrogen.cc#new... src/hydrogen.cc:3864: BoundsCheckValueInfo* NextInBasicBlock() { return next_in_basic_block_; } nit: lower-case names for simple accessors. https://chromiumcodereview.appspot.com/11415173/diff/2001/src/hydrogen.cc#new... src/hydrogen.cc:3881: // instructions so that it is easy to change than again if needed. s/than/them/ https://chromiumcodereview.appspot.com/11415173/diff/2001/src/hydrogen.cc#new... src/hydrogen.cc:3882: bool CoverCheckWithBase( nit: for method declarations (as opposed to calls), either everything should fit on one line, or every parameter should be on its own line. Also, I don't like this method's name. It doesn't make it clear what the method does, and it also doesn't indicate what it returns. At the very least, a comment "Returns true iff the new_check should be removed." would be nice. https://chromiumcodereview.appspot.com/11415173/diff/2001/src/hydrogen.cc#new... src/hydrogen.cc:3885: bool remove_new_check = false; Why do we need a variable for this? Looks like assigning it is always the last thing that happens before returning, so you could s/remove_new_check = true;/return true;/ below and finally s/return remove_new_check;/return false;/. https://chromiumcodereview.appspot.com/11415173/diff/2001/src/hydrogen.cc#new... src/hydrogen.cc:3894: upper_check_->Check()->block() != BasicBlock()) { Why is this check necessary? BoundsCheckValueInfo is per-block anyway, so why can't you ignore checks from the wrong block in the first place? https://chromiumcodereview.appspot.com/11415173/diff/2001/src/hydrogen.cc#new... src/hydrogen.cc:3967: value_info != NULL; nit: aligning "value_info" with "BoundsCheckValueInfo" (i.e. one more space) looks slightly better, don't you think? https://chromiumcodereview.appspot.com/11415173/diff/2001/src/hydrogen.cc#new... src/hydrogen.cc:3974: if (upper_covered != NULL) { Ugh. 5 levels of nested "if"s? I'd prefer the following (even though it's still messy): if (upper_covered != NULL && value_info->Relation() == LT) { HValue* constraint = value_info->Constraint(); if (constraint == limit) { *upper_covered = true; continue; } if (hoisted_limit != NULL && constraint->block()->Dominates( block->loop_information()->loop_header()) && (*hoisted_limit == NULL || constraint->block()->Dominates( (*hoisted_limit)->block()))) { *hoisted_limit = constraint; } } https://chromiumcodereview.appspot.com/11415173/diff/2001/src/hydrogen.cc#new... src/hydrogen.cc:3993: (upper_covered == NULL || *upper_covered))) { Please indent this so that the indentation reflects the nesting structure (i.e. two more spaces). Also, I think it would be a bit clearer to move the negation into the leaves: if ((lower_covered != NULL && *lower_covered == false) || (upper_covered != NULL && *upper_covered == false)) { https://chromiumcodereview.appspot.com/11415173/diff/2001/src/hydrogen.cc#new... src/hydrogen.cc:4007: if (!((lower_covered == NULL || *lower_covered) && same here https://chromiumcodereview.appspot.com/11415173/diff/2001/src/hydrogen.cc#new... src/hydrogen.cc:4036: static bool CoverBasePlusConstant(HBoundsCheck* check, Another method that doesn't tell me what the method does (what does "cover" mean?) or what it returns. https://chromiumcodereview.appspot.com/11415173/diff/2001/src/hydrogen.cc#new... src/hydrogen.cc:4049: } else { nit: no need for "else", just "return false". https://chromiumcodereview.appspot.com/11415173/diff/2001/src/hydrogen.cc#new... src/hydrogen.cc:4062: HValue** hoisted_limit_pointer; initialize this to NULL here... https://chromiumcodereview.appspot.com/11415173/diff/2001/src/hydrogen.cc#new... src/hydrogen.cc:4069: hoisted_limit_pointer = NULL; ...and drop this. https://chromiumcodereview.appspot.com/11415173/diff/2001/src/hydrogen.cc#new... src/hydrogen.cc:4073: index, length, block, hoisted_limit_pointer, nit: no need to break the first line of arguments https://chromiumcodereview.appspot.com/11415173/diff/2001/src/hydrogen.cc#new... src/hydrogen.cc:4083: if ((!(lower_covered && upper_covered)) && hoisted_limit != NULL) { simplification: you can remove one set of parentheses by moving the negation to the leaves of the condition tree: if ((!lower_covered || !upper_covered) && hoisted_limit != NULL) { https://chromiumcodereview.appspot.com/11415173/diff/2001/src/hydrogen.cc#new... src/hydrogen.cc:4088: hoisting_context->block() != hoisting_block) { nit: prefer alignment at '(' (i.e. in this case the two occurrences of "hosting_context" exactly below each other). https://chromiumcodereview.appspot.com/11415173/diff/2001/src/hydrogen.cc#new... src/hydrogen.cc:4119: static void FromPhi(HPhi* phi, nit: some other name please. We commonly use "static Foo* Foo::FromBar(Bar* bar)" as the name of a factory method that constructs a Foo from a Bar. https://chromiumcodereview.appspot.com/11415173/diff/2001/src/hydrogen.cc#new... src/hydrogen.cc:4142: static void FromConditionalBranch( Again, please choose some name that doesn't sound like a factory method https://chromiumcodereview.appspot.com/11415173/diff/2001/src/hydrogen.cc#new... src/hydrogen.cc:4148: bool isElseBranch; nit: unix_hacker_style names for variables https://chromiumcodereview.appspot.com/11415173/diff/2001/src/hydrogen.cc#new... src/hydrogen.cc:4169: context->NewValueInfo(constraint, value, Switched(relation), false); Whoa. Do we really need to store every fact twice? https://chromiumcodereview.appspot.com/11415173/diff/2001/src/hydrogen.cc#new... src/hydrogen.cc:4188: default: since you're handling all cases explicitly, you don't need a "default:" case. Which is preferable anyway, because it turns the UNREACHABLE() run-time error into a compile-time error. https://chromiumcodereview.appspot.com/11415173/diff/2001/src/hydrogen.cc#new... src/hydrogen.cc:4195: *previous_for_value_ = next_for_value_; Having different levels of pointer indirection for previous_for_value_ and next_for_value_ is horribly confusing. https://chromiumcodereview.appspot.com/11415173/diff/2001/src/hydrogen.cc#new... src/hydrogen.cc:4206: BoundsCheckValueInfo(HValue* v, nit: constructor should be the first thing in the "public:" section https://chromiumcodereview.appspot.com/11415173/diff/2001/src/hydrogen.cc#new... src/hydrogen.cc:4207: HValue* c, what do "v" and "c" mean? https://chromiumcodereview.appspot.com/11415173/diff/2001/src/hydrogen.cc#new... src/hydrogen.cc:4212: int check_offset = 0) : nit: ':' goes on the next line https://chromiumcodereview.appspot.com/11415173/diff/2001/src/hydrogen.cc#new... src/hydrogen.cc:4221: lower_check_(next_for_value_ != NULL ? nit: if a ternary operator doesn't fit on one line, align '?' and ':', as in: fooooooooooooooooo ? barrrrrrrrrrrrrrrrr : bazzzzzzzzzzzzzzzzz https://chromiumcodereview.appspot.com/11415173/diff/2001/src/hydrogen.cc#new... src/hydrogen.cc:4233: HValue* value_; nit: member variables come last in the "private:" section https://chromiumcodereview.appspot.com/11415173/diff/2001/src/hydrogen.cc#new... src/hydrogen.cc:4248: static bool GetCheckIndexBase(HValue* index, Another method name that puzzles me, especially in combination with the comment above which seems to say something completely different. https://chromiumcodereview.appspot.com/11415173/diff/2001/src/hydrogen.cc#new... src/hydrogen.cc:4270: if (sub->left()->IsConstant()) { This was probably supposed to be sub->right()->IsConstant(), no? It seems that would be the case much more often, and it matches what you're doing below. https://chromiumcodereview.appspot.com/11415173/diff/2001/src/hydrogen.cc#new... src/hydrogen.cc:4286: bool* skip_lower, nit: indentation https://chromiumcodereview.appspot.com/11415173/diff/2001/src/hydrogen.cc#new... src/hydrogen.cc:4295: if (add->left()->IsConstant()) { This code here is an almost exact duplicate of the code in GetCheckIndexBase above. I would suggest to replace it with a call, or factor out the shared stuff. https://chromiumcodereview.appspot.com/11415173/diff/2001/src/hydrogen.cc#new... src/hydrogen.cc:4328: } else if (*constant > 0) { This is the same condition as before. You probably meant "if (*constant < 0)". Also, if sub->left()->IsConstant() above, this code almost certainly doesn't do what you want. https://chromiumcodereview.appspot.com/11415173/diff/2001/src/hydrogen.cc#new... src/hydrogen.cc:4342: static ValueInfoRelation FromToken(Token::Value token) { Having such a simple mapping from Token::Value to ValueInfoRelation makes me wonder why you're not using Token::Value in the first place? We have Token::IsOrderedRelationalCompareOp(), Token::IsEqualityOp(), Token::NegateCompareOp(), Token::String(), which should cover all of your use cases quite nicely. https://chromiumcodereview.appspot.com/11415173/diff/2001/src/hydrogen.cc#new... src/hydrogen.cc:4365: HPhi* base, HValue* operation, bool* value_increment) { nit: for method/function declarations, either everything fits onto one line, or each parameter gets its own line (except the first if it fits on the line of the method name and the others can be aligned with that). https://chromiumcodereview.appspot.com/11415173/diff/2001/src/hydrogen.cc#new... src/hydrogen.cc:4369: HAdd* add = HAdd::cast(operation); nit: indentation https://chromiumcodereview.appspot.com/11415173/diff/2001/src/hydrogen.cc#new... src/hydrogen.cc:4381: if ((c->DoubleValue() == 1) || (c->DoubleValue() == -1)) Again: 1) why DoubleValue() and not Integer32Value()? 2) you need to check for HasDoubleValue() (or HasInteger32Value()) for this to work correctly. https://chromiumcodereview.appspot.com/11415173/diff/2001/src/hydrogen.cc#new... src/hydrogen.cc:4396: if (sub->right() == base && sub->left()->IsConstant()) { this looks like another left/right mixup. https://chromiumcodereview.appspot.com/11415173/diff/2001/src/hydrogen.cc#new... src/hydrogen.cc:4416: static ValueInfoRelation Switched(ValueInfoRelation other) { "Switched"? Into shuffle mode? Also, we already have Token::NegateCompareOp() https://chromiumcodereview.appspot.com/11415173/diff/2001/src/hydrogen.cc#new... src/hydrogen.cc:4454: HValue* c, what do "v" and "c" stand for? https://chromiumcodereview.appspot.com/11415173/diff/2001/src/hydrogen.cc#new... src/hydrogen.cc:4496: ZoneAllocationPolicy(zone()))->value)); nit: please align with "key" https://chromiumcodereview.appspot.com/11415173/diff/2001/src/hydrogen.cc#new... src/hydrogen.cc:4524: BoundsCheckValueInfo::FromConditionalBranch( Looks like "static void Foo::Bar(..., Baz*)" could be made cleaner by refactoring it to "void Baz::Bar(...)", i.e. BoundsCheckRemovalBlockContext::HandleConditionalBranch(HCompareIdAndBranch* branch). https://chromiumcodereview.appspot.com/11415173/diff/2001/src/hydrogen.cc#new... src/hydrogen.cc:4531: BoundsCheckValueInfo::FromPhi(bb->phis()->at(i), &context); again, why "void A::B(C, &context)" instead of "context->B(C)"? https://chromiumcodereview.appspot.com/11415173/diff/2001/src/hydrogen.cc#new... src/hydrogen.cc:4538: check->ReplaceAllUsesWith(check->index()); Why this line? https://chromiumcodereview.appspot.com/11415173/diff/2001/src/hydrogen.cc#new... src/hydrogen.cc:4539: BoundsCheckValueInfo::HandleCheck(check, &context); again, why "void A::B(C, &context)" instead of "context->B(C)"? https://chromiumcodereview.appspot.com/11415173/diff/2001/src/hydrogen.cc#new... src/hydrogen.cc:4548: value_info != NULL; nit: aligning 'v' with 'B' looks better
Description was changed from ========== Array bounds check elimination. BUG= ========== to ========== Array bounds check elimination. BUG= ========== |
||||||||||||||||||||||||||||||||||||||||||||||||
