A change in the way we place TransitionElementKinds in the tree.

A change in the way we place TransitionElementKinds in the tree.
I attempt to place them as close to object definition as possible, in the
hopes of getting them out of loops.

There is currently a weakness that the deferment isn't strongly tied to the 
creation of a DeferredTransition structure. There are currently some failing 
tests because of this.

BUG=

[mvstanton, 2012-11-09 16:06:59]

Hi guys,
This code is not ready for prime time yet, I expect to make a few more important
revisions Monday and Tuesday. But the functionality is there. The "meat" is in
hydrogen.cc, where the list of DeferredTransitions are processed to find
Terminal Nodes (my term), to negotiate the unified and maximum ElementsKind
(to->from) span, to patch the graph appropriately.

The "chaining" of outputs through the transitions we discussed the other day is
not in place, but adequate dependency management should allow me to save that
for a follow-on checkin.

Something I need to think about over the weekend is that I try to select
HLoad/StoreKeyed nodes carefully for deferred initialization, but this happens
far enough away from the place where I decide if an attempt at transition
deferment should be run that I have an error. These need to be tightly coupled.

So not ready for review, but if you see anything really out there you could let
me know, thx!

[danno, 2012-11-14 15:28:18]

A first round of comments

https://codereview.chromium.org/11365174/diff/1/src/compiler.cc
File src/compiler.cc (right):

https://codereview.chromium.org/11365174/diff/1/src/compiler.cc#newcode354
src/compiler.cc:354: // to test my changes.
Looks like you can get rid of this :-)

https://codereview.chromium.org/11365174/diff/1/src/elements-kind.cc
File src/elements-kind.cc (right):

https://codereview.chromium.org/11365174/diff/1/src/elements-kind.cc#newcode141
src/elements-kind.cc:141: ASSERT(IsFastElementsKind(e2));
I think you can simplify this code:

int i1 = GetSequenceIndexFromFastElementsKind(e1);
int i2 = GetSequenceIndexFromFastElementsKind(e2);

ElementsKind result = GetFastElementsKindFromSequenceIndex(max(i1, i2);
return ((IsFastHoleyElementKind(e1) != IsFastHoleyElementsKind(e2))
 ? GetHoleyElementsKind(result)
 : result;

https://codereview.chromium.org/11365174/diff/1/src/elements-kind.h
File src/elements-kind.h (right):

https://codereview.chromium.org/11365174/diff/1/src/elements-kind.h#newcode214
src/elements-kind.h:214: ElementsKind GetUnifiedFastElementsKind(ElementsKind
e1, ElementsKind e2);
kind1, kind2? Perhaps a comment what this fellow does?

https://codereview.chromium.org/11365174/diff/1/src/flag-definitions.h
File src/flag-definitions.h (right):

https://codereview.chromium.org/11365174/diff/1/src/flag-definitions.h#newcod...
src/flag-definitions.h:194: DEFINE_bool(trace_transition_placement, false,
"trace elementskind transition placement")
80 col

https://codereview.chromium.org/11365174/diff/1/src/hydrogen-instructions.h
File src/hydrogen-instructions.h (right):

https://codereview.chromium.org/11365174/diff/1/src/hydrogen-instructions.h#n...
src/hydrogen-instructions.h:2224: bool has_typecheck() const { return
OperandAt(0) != OperandAt(1); }
HasTypeCheck()

https://codereview.chromium.org/11365174/diff/1/src/hydrogen-instructions.h#n...
src/hydrogen-instructions.h:4267: bool defer_initialization=false)
nit: separate all operators from variable names and expressions with spaces

https://codereview.chromium.org/11365174/diff/1/src/hydrogen-instructions.h#n...
src/hydrogen-instructions.h:4356: void InitializeFields() {
Move implementation this to the .cc file. 

And oh... Drop the "Fields." Just "Initialize." It's cleaner. ;-)

https://codereview.chromium.org/11365174/diff/1/src/hydrogen-instructions.h#n...
src/hydrogen-instructions.h:4551: bool defer_initialization=false)
spaces b/a =

https://codereview.chromium.org/11365174/diff/1/src/hydrogen-instructions.h#n...
src/hydrogen-instructions.h:4635: void InitializeFlags() {
Again, how about just "Initialize"?

https://codereview.chromium.org/11365174/diff/1/src/hydrogen.cc
File src/hydrogen.cc (right):

https://codereview.chromium.org/11365174/diff/1/src/hydrogen.cc#newcode2512
src/hydrogen.cc:2512: class HighestMapAndFamily {
When you say "highest", do you mean most general? That's a term that we use
elsewhere for elements kind, and you might want to be consistent.

https://codereview.chromium.org/11365174/diff/1/src/hydrogen.cc#newcode2523
src/hydrogen.cc:2523: void change(Map* new_highest_map, Map* new_family) {
Maybe "Update" instead?

https://codereview.chromium.org/11365174/diff/1/src/hydrogen.cc#newcode2539
src/hydrogen.cc:2539: bool operator==(const HighestMapAndFamily& h) const {
We tend to avoid operator== (see
http://google-styleguide.googlecode.com/svn/trunk/cppguide.xml#Operator_Overl...).
"Equals" is more consistent with other sites?

https://codereview.chromium.org/11365174/diff/1/src/hydrogen.cc#newcode2546
src/hydrogen.cc:2546: bool operator!=(const HighestMapAndFamily& h) const {
operator overloading

https://codereview.chromium.org/11365174/diff/1/src/hydrogen.cc#newcode2550
src/hydrogen.cc:2550: HighestMapAndFamily& operator=(const HighestMapAndFamily&
h) {
operator overloading

https://codereview.chromium.org/11365174/diff/1/src/hydrogen.cc#newcode2559
src/hydrogen.cc:2559: Map *highest_map_;
Map* highest_map_

https://codereview.chromium.org/11365174/diff/1/src/hydrogen.cc#newcode2565
src/hydrogen.cc:2565: class TerminalMapValue: public ZoneObject {
TransitionElementsInputValueData?

https://codereview.chromium.org/11365174/diff/1/src/hydrogen.cc#newcode2575
src/hydrogen.cc:2575: void add_transition(DeferredTransitions* todo) {
AddTransition

https://codereview.chromium.org/11365174/diff/1/src/hydrogen.cc#newcode2585
src/hydrogen.cc:2585: ElementsKind highest_elementskind() const {
GetMostGenerateElementsKind()?

https://codereview.chromium.org/11365174/diff/1/src/hydrogen.cc#newcode2627
src/hydrogen.cc:2627: HInstruction* terminal_node_;
HValue*

https://codereview.chromium.org/11365174/diff/1/src/hydrogen.cc#newcode2745
src/hydrogen.cc:2745: void
FinalizeTransitionToDos(ZoneList<DeferredTransitions>& transitions, int
maximumGraphID) {
How about FinalizeDeferredTransitionElements?

https://codereview.chromium.org/11365174/diff/1/src/hydrogen.cc#newcode2749
src/hydrogen.cc:2749: // Also fill in the current highest, which may later be
changed externally.
most general?

https://codereview.chromium.org/11365174/diff/1/src/hydrogen.cc#newcode2811
src/hydrogen.cc:2811: // "floor" of the map tree, then all transitions involving
those terminal
to abuse the metaphor even more, maybe "trunk" instead of "floor"

https://codereview.chromium.org/11365174/diff/1/src/hydrogen.cc#newcode2811
src/hydrogen.cc:2811: // "floor" of the map tree, then all transitions involving
those terminal
pre-transitioned input value?

https://codereview.chromium.org/11365174/diff/1/src/hydrogen.cc#newcode2814
src/hydrogen.cc:2814: ZoneHashMap terminalMap(TerminalMatch,32,allocator);
spaces after ,s

https://codereview.chromium.org/11365174/diff/1/src/hydrogen.h
File src/hydrogen.h (right):

https://codereview.chromium.org/11365174/diff/1/src/hydrogen.h#newcode243
src/hydrogen.h:243: class TransitionRecord BASE_EMBEDDED {
I hate being overly fussy about names, but they are important. How about these
bad suggestions:
TransitionElementsMemento?
TransitionElementsBookmark?
PontentialTransitionElements?
I guess what's missing in the name is what kind of name (therefore + "Elements")
and what it actually does: remembers that a transition needs to be accounted for
later (e.g. "Memento"). You can probably do better than I, tho.

https://codereview.chromium.org/11365174/diff/1/src/hydrogen.h#newcode245
src/hydrogen.h:245: TransitionRecord(HTransitionElementsKind* transition_instr,
Handle<Map> map_from,
80 col

https://codereview.chromium.org/11365174/diff/1/src/hydrogen.h#newcode251
src/hydrogen.h:251: Handle<Map>& map_to_ref() { return map_to_; }
We really avoid & (refs) everywhere else in the code. Does this allow you to
change the map? If so, add a set_map_to method.

https://codereview.chromium.org/11365174/diff/1/src/hydrogen.h#newcode254
src/hydrogen.h:254: Handle<Map>& optimistic_holey_ref() { return
optimistic_holey_; }
Again, please void the ref.

https://codereview.chromium.org/11365174/diff/1/src/hydrogen.h#newcode257
src/hydrogen.h:257: bool equal(const TransitionRecord& other) const {
Equals

https://codereview.chromium.org/11365174/diff/1/src/hydrogen.h#newcode263
src/hydrogen.h:263: HTransitionElementsKind* transition_instr_;
Just transition_?

https://codereview.chromium.org/11365174/diff/1/src/hydrogen.h#newcode264
src/hydrogen.h:264: Handle<Map> map_from_;
how about just "from_", "to_", "family_"

https://codereview.chromium.org/11365174/diff/1/src/hydrogen.h#newcode267
src/hydrogen.h:267: Handle<Map> optimistic_holey_;
Isn't this the "pesimistic_holey_" map? i.e. the one you will have to use in the
worst case?

https://codereview.chromium.org/11365174/diff/1/src/hydrogen.h#newcode271
src/hydrogen.h:271: typedef ZoneList<HInstruction*> TerminalNodeList;
Are these HInstructions or HValues? If it's just HValues, then move this typedef
into hydrogen-instructions, and call it simply HValueList.

https://codereview.chromium.org/11365174/diff/1/src/hydrogen.h#newcode273
src/hydrogen.h:273: class DeferredTransitions BASE_EMBEDDED {
PontentialTransitionElementsGroup?

https://codereview.chromium.org/11365174/diff/1/src/hydrogen.h#newcode275
src/hydrogen.h:275: DeferredTransitions(HInstruction* keyedInstr, HCheckNonSmi*
checknonsmi,
keyed_instruction and other style guide stuff on other parameters.

https://codereview.chromium.org/11365174/diff/1/src/hydrogen.h#newcode277
src/hydrogen.h:277: : zone_(zone), keyed_instr_(keyedInstr),
checknonsmi_instr_(checknonsmi),
In general, for variables and members, separate every word with a "_" and no
abbreviations if possible, so "check_non_smi_instruction_" and check_non_smi

https://codereview.chromium.org/11365174/diff/1/src/hydrogen.h#newcode293
src/hydrogen.h:293: void add_transitions(const ZoneList<TransitionRecord>&
records) {
"AddTransitions". Only trivial variable accessors (get/set) should be lower case
and use "_", all other method names should be CamelCase

https://codereview.chromium.org/11365174/diff/1/src/hydrogen.h#newcode325
src/hydrogen.h:325: SCORE_NEUTRAL
, SCORE_TYPE_COUNT  // Must be last

https://codereview.chromium.org/11365174/diff/1/src/hydrogen.h#newcode347
src/hydrogen.h:347:
HLoadKeyed::cast(instr())->PerformDeferredInitialization(elements_kind);
Is it possible to move PerformDeferredInitialization into
ArrayInstructionInterface?

https://codereview.chromium.org/11365174/diff/1/src/hydrogen.h#newcode375
src/hydrogen.h:375: HInstruction *keyed_instr_;
load_or_store_?

https://codereview.chromium.org/11365174/diff/1/src/hydrogen.h#newcode376
src/hydrogen.h:376: HCheckNonSmi* checknonsmi_instr_;
how about just smi_check_?

https://codereview.chromium.org/11365174/diff/1/src/hydrogen.h#newcode377
src/hydrogen.h:377: HCheckMaps* checkmaps_instr_;
map_check_?

https://codereview.chromium.org/11365174/diff/1/src/hydrogen.h#newcode379
src/hydrogen.h:379: int score_[3];
score_[SCORE_TYPE_COUNT]

https://codereview.chromium.org/11365174/diff/1/src/hydrogen.h#newcode382
src/hydrogen.h:382: TerminalNodeList *terminal_nodes_;
I think "Terminal" might not be the right to use. I think something like
"pre_transitioned_values_" might be better.

https://codereview.chromium.org/11365174/diff/1/src/hydrogen.h#newcode1014
src/hydrogen.h:1014: 
nit: extra whitespace :-)

https://codereview.chromium.org/11365174/diff/1/src/hydrogen.h#newcode1300
src/hydrogen.h:1300: HCheckMaps** checkmap_instr=NULL);
extra <sp> around =

https://codereview.chromium.org/11365174/diff/1/src/objects.cc
File src/objects.cc (right):

https://codereview.chromium.org/11365174/diff/1/src/objects.cc#newcode2340
src/objects.cc:2340: MaybeObject* AddMissingElementsTransitions(Map* map,
ElementsKind to_kind) {
Perhaps it is time to move this to be part of the Map class' interface?

[mvstanton, 2012-11-16 15:15:05]

Hi Danno, hi Toon and Michael,
Okay here is the change. Two pieces missing:
1) a unit test that demonstrates that we recognize the ideal elements kind from
the start of the method.
2) There is a heap corruption bug in one benchmark.

But the outlines should survive at this point. You won't waste your time to have
a look. Thanks!
--Michael

https://codereview.chromium.org/11365174/diff/1/src/compiler.cc
File src/compiler.cc (right):

https://codereview.chromium.org/11365174/diff/1/src/compiler.cc#newcode354
src/compiler.cc:354: // to test my changes.
On 2012/11/14 15:28:18, danno wrote:
> Looks like you can get rid of this :-)

Done.

https://codereview.chromium.org/11365174/diff/1/src/elements-kind.cc
File src/elements-kind.cc (right):

https://codereview.chromium.org/11365174/diff/1/src/elements-kind.cc#newcode141
src/elements-kind.cc:141: ASSERT(IsFastElementsKind(e2));
On 2012/11/14 15:28:18, danno wrote:
> I think you can simplify this code:
> 
> int i1 = GetSequenceIndexFromFastElementsKind(e1);
> int i2 = GetSequenceIndexFromFastElementsKind(e2);
> 
> ElementsKind result = GetFastElementsKindFromSequenceIndex(max(i1, i2);
> return ((IsFastHoleyElementKind(e1) != IsFastHoleyElementsKind(e2))
>  ? GetHoleyElementsKind(result)
>  : result;

Done.

https://codereview.chromium.org/11365174/diff/1/src/elements-kind.h
File src/elements-kind.h (right):

https://codereview.chromium.org/11365174/diff/1/src/elements-kind.h#newcode214
src/elements-kind.h:214: ElementsKind GetUnifiedFastElementsKind(ElementsKind
e1, ElementsKind e2);
On 2012/11/14 15:28:18, danno wrote:
> kind1, kind2? Perhaps a comment what this fellow does?

Done.

https://codereview.chromium.org/11365174/diff/1/src/flag-definitions.h
File src/flag-definitions.h (right):

https://codereview.chromium.org/11365174/diff/1/src/flag-definitions.h#newcod...
src/flag-definitions.h:194: DEFINE_bool(trace_transition_placement, false,
"trace elementskind transition placement")
On 2012/11/14 15:28:18, danno wrote:
> 80 col

Done.

https://codereview.chromium.org/11365174/diff/1/src/hydrogen-instructions.h
File src/hydrogen-instructions.h (right):

https://codereview.chromium.org/11365174/diff/1/src/hydrogen-instructions.h#n...
src/hydrogen-instructions.h:2224: bool has_typecheck() const { return
OperandAt(0) != OperandAt(1); }
On 2012/11/14 15:28:18, danno wrote:
> HasTypeCheck()

Done.

https://codereview.chromium.org/11365174/diff/1/src/hydrogen-instructions.h#n...
src/hydrogen-instructions.h:4267: bool defer_initialization=false)
On 2012/11/14 15:28:18, danno wrote:
> nit: separate all operators from variable names and expressions with spaces

Done.

https://codereview.chromium.org/11365174/diff/1/src/hydrogen-instructions.h#n...
src/hydrogen-instructions.h:4356: void InitializeFields() {
On 2012/11/14 15:28:18, danno wrote:
> Move implementation this to the .cc file. 
> 
> And oh... Drop the "Fields." Just "Initialize." It's cleaner. ;-)

Done.

https://codereview.chromium.org/11365174/diff/1/src/hydrogen-instructions.h#n...
src/hydrogen-instructions.h:4551: bool defer_initialization=false)
On 2012/11/14 15:28:18, danno wrote:
> spaces b/a =

Done.

https://codereview.chromium.org/11365174/diff/1/src/hydrogen-instructions.h#n...
src/hydrogen-instructions.h:4635: void InitializeFlags() {
On 2012/11/14 15:28:18, danno wrote:
> Again, how about just "Initialize"?

Done.

https://codereview.chromium.org/11365174/diff/1/src/hydrogen.cc
File src/hydrogen.cc (right):

https://codereview.chromium.org/11365174/diff/1/src/hydrogen.cc#newcode2512
src/hydrogen.cc:2512: class HighestMapAndFamily {
On 2012/11/14 15:28:18, danno wrote:
> When you say "highest", do you mean most general? That's a term that we use
> elsewhere for elements kind, and you might want to be consistent.

I needed to update many locations to be consistent about this. Good advice, thx.

https://codereview.chromium.org/11365174/diff/1/src/hydrogen.cc#newcode2523
src/hydrogen.cc:2523: void change(Map* new_highest_map, Map* new_family) {
On 2012/11/14 15:28:18, danno wrote:
> Maybe "Update" instead?

Done.

https://codereview.chromium.org/11365174/diff/1/src/hydrogen.cc#newcode2539
src/hydrogen.cc:2539: bool operator==(const HighestMapAndFamily& h) const {
On 2012/11/14 15:28:18, danno wrote:
> We tend to avoid operator== (see
>
http://google-styleguide.googlecode.com/svn/trunk/cppguide.xml#Operator_Overl...).
> "Equals" is more consistent with other sites?

Done.

https://codereview.chromium.org/11365174/diff/1/src/hydrogen.cc#newcode2546
src/hydrogen.cc:2546: bool operator!=(const HighestMapAndFamily& h) const {
On 2012/11/14 15:28:18, danno wrote:
> operator overloading

Done.

https://codereview.chromium.org/11365174/diff/1/src/hydrogen.cc#newcode2550
src/hydrogen.cc:2550: HighestMapAndFamily& operator=(const HighestMapAndFamily&
h) {
On 2012/11/14 15:28:18, danno wrote:
> operator overloading

this one I need to keep in order to copy these things. If it's all too much I
could just revert to thinking about the maps as two separate pointers and
abandon this little type.

https://codereview.chromium.org/11365174/diff/1/src/hydrogen.cc#newcode2559
src/hydrogen.cc:2559: Map *highest_map_;
On 2012/11/14 15:28:18, danno wrote:
> Map* highest_map_

Done.

https://codereview.chromium.org/11365174/diff/1/src/hydrogen.cc#newcode2565
src/hydrogen.cc:2565: class TerminalMapValue: public ZoneObject {
On 2012/11/14 15:28:18, danno wrote:
> TransitionElementsInputValueData?

Done.

https://codereview.chromium.org/11365174/diff/1/src/hydrogen.cc#newcode2575
src/hydrogen.cc:2575: void add_transition(DeferredTransitions* todo) {
On 2012/11/14 15:28:18, danno wrote:
> AddTransition

Done.

https://codereview.chromium.org/11365174/diff/1/src/hydrogen.cc#newcode2585
src/hydrogen.cc:2585: ElementsKind highest_elementskind() const {
On 2012/11/14 15:28:18, danno wrote:
> GetMostGenerateElementsKind()?

removed method, no callers

https://codereview.chromium.org/11365174/diff/1/src/hydrogen.cc#newcode2627
src/hydrogen.cc:2627: HInstruction* terminal_node_;
On 2012/11/14 15:28:18, danno wrote:
> HValue*

Done.

https://codereview.chromium.org/11365174/diff/1/src/hydrogen.cc#newcode2745
src/hydrogen.cc:2745: void
FinalizeTransitionToDos(ZoneList<DeferredTransitions>& transitions, int
maximumGraphID) {
On 2012/11/14 15:28:18, danno wrote:
> How about FinalizeDeferredTransitionElements?

Done.

https://codereview.chromium.org/11365174/diff/1/src/hydrogen.cc#newcode2749
src/hydrogen.cc:2749: // Also fill in the current highest, which may later be
changed externally.
On 2012/11/14 15:28:18, danno wrote:
> most general?

Done.

https://codereview.chromium.org/11365174/diff/1/src/hydrogen.cc#newcode2814
src/hydrogen.cc:2814: ZoneHashMap terminalMap(TerminalMatch,32,allocator);
On 2012/11/14 15:28:18, danno wrote:
> spaces after ,s

Done.

https://codereview.chromium.org/11365174/diff/1/src/hydrogen.h
File src/hydrogen.h (right):

https://codereview.chromium.org/11365174/diff/1/src/hydrogen.h#newcode243
src/hydrogen.h:243: class TransitionRecord BASE_EMBEDDED {
On 2012/11/14 15:28:18, danno wrote:
> I hate being overly fussy about names, but they are important. How about these
> bad suggestions:
> TransitionElementsMemento?
> TransitionElementsBookmark?
> PontentialTransitionElements?
> I guess what's missing in the name is what kind of name (therefore +
"Elements")
> and what it actually does: remembers that a transition needs to be accounted
for
> later (e.g. "Memento"). You can probably do better than I, tho.

Bad suggestion TransitionElementsBookmark sounds perfect.

https://codereview.chromium.org/11365174/diff/1/src/hydrogen.h#newcode245
src/hydrogen.h:245: TransitionRecord(HTransitionElementsKind* transition_instr,
Handle<Map> map_from,
On 2012/11/14 15:28:18, danno wrote:
> 80 col

Done.

https://codereview.chromium.org/11365174/diff/1/src/hydrogen.h#newcode251
src/hydrogen.h:251: Handle<Map>& map_to_ref() { return map_to_; }
On 2012/11/14 15:28:18, danno wrote:
> We really avoid & (refs) everywhere else in the code. Does this allow you to
> change the map? If so, add a set_map_to method.

Done.

https://codereview.chromium.org/11365174/diff/1/src/hydrogen.h#newcode254
src/hydrogen.h:254: Handle<Map>& optimistic_holey_ref() { return
optimistic_holey_; }
On 2012/11/14 15:28:18, danno wrote:
> Again, please void the ref.

Done.

https://codereview.chromium.org/11365174/diff/1/src/hydrogen.h#newcode257
src/hydrogen.h:257: bool equal(const TransitionRecord& other) const {
On 2012/11/14 15:28:18, danno wrote:
> Equals

Done.

https://codereview.chromium.org/11365174/diff/1/src/hydrogen.h#newcode263
src/hydrogen.h:263: HTransitionElementsKind* transition_instr_;
On 2012/11/14 15:28:18, danno wrote:
> Just transition_?

Done.

https://codereview.chromium.org/11365174/diff/1/src/hydrogen.h#newcode264
src/hydrogen.h:264: Handle<Map> map_from_;
On 2012/11/14 15:28:18, danno wrote:
> how about just "from_", "to_", "family_" 

Done.

https://codereview.chromium.org/11365174/diff/1/src/hydrogen.h#newcode267
src/hydrogen.h:267: Handle<Map> optimistic_holey_;
On 2012/11/14 15:28:18, danno wrote:
> Isn't this the "pesimistic_holey_" map? i.e. the one you will have to use in
the
> worst case?

Done.

https://codereview.chromium.org/11365174/diff/1/src/hydrogen.h#newcode271
src/hydrogen.h:271: typedef ZoneList<HInstruction*> TerminalNodeList;
On 2012/11/14 15:28:18, danno wrote:
> Are these HInstructions or HValues? If it's just HValues, then move this
typedef
> into hydrogen-instructions, and call it simply HValueList.

I do treat them as HInstructions a few times...

https://codereview.chromium.org/11365174/diff/1/src/hydrogen.h#newcode273
src/hydrogen.h:273: class DeferredTransitions BASE_EMBEDDED {
On 2012/11/14 15:28:18, danno wrote:
> PontentialTransitionElementsGroup?

I went with MarkedTransitionElementsGroup. "marking" and "bookmarks" maybe that
is a good metaphor. We mark them, and might later use them to optimize, or maybe
not.

https://codereview.chromium.org/11365174/diff/1/src/hydrogen.h#newcode275
src/hydrogen.h:275: DeferredTransitions(HInstruction* keyedInstr, HCheckNonSmi*
checknonsmi,
On 2012/11/14 15:28:18, danno wrote:
> keyed_instruction and other style guide stuff on other parameters.

Done.

https://codereview.chromium.org/11365174/diff/1/src/hydrogen.h#newcode277
src/hydrogen.h:277: : zone_(zone), keyed_instr_(keyedInstr),
checknonsmi_instr_(checknonsmi),
On 2012/11/14 15:28:18, danno wrote:
> In general, for variables and members, separate every word with a "_" and no
> abbreviations if possible, so "check_non_smi_instruction_" and check_non_smi

Done.

https://codereview.chromium.org/11365174/diff/1/src/hydrogen.h#newcode293
src/hydrogen.h:293: void add_transitions(const ZoneList<TransitionRecord>&
records) {
On 2012/11/14 15:28:18, danno wrote:
> "AddTransitions". Only trivial variable accessors (get/set) should be lower
case
> and use "_", all other method names should be CamelCase

Done.

https://codereview.chromium.org/11365174/diff/1/src/hydrogen.h#newcode325
src/hydrogen.h:325: SCORE_NEUTRAL
On 2012/11/14 15:28:18, danno wrote:
> , SCORE_TYPE_COUNT  // Must be last

Done.

https://codereview.chromium.org/11365174/diff/1/src/hydrogen.h#newcode347
src/hydrogen.h:347:
HLoadKeyed::cast(instr())->PerformDeferredInitialization(elements_kind);
On 2012/11/14 15:28:18, danno wrote:
> Is it possible to move PerformDeferredInitialization into
> ArrayInstructionInterface?

Done.

https://codereview.chromium.org/11365174/diff/1/src/hydrogen.h#newcode375
src/hydrogen.h:375: HInstruction *keyed_instr_;
On 2012/11/14 15:28:18, danno wrote:
> load_or_store_?

Done.

https://codereview.chromium.org/11365174/diff/1/src/hydrogen.h#newcode376
src/hydrogen.h:376: HCheckNonSmi* checknonsmi_instr_;
On 2012/11/14 15:28:18, danno wrote:
> how about just smi_check_?

Done.

https://codereview.chromium.org/11365174/diff/1/src/hydrogen.h#newcode377
src/hydrogen.h:377: HCheckMaps* checkmaps_instr_;
On 2012/11/14 15:28:18, danno wrote:
> map_check_?

Done.

https://codereview.chromium.org/11365174/diff/1/src/hydrogen.h#newcode379
src/hydrogen.h:379: int score_[3];
On 2012/11/14 15:28:18, danno wrote:
> score_[SCORE_TYPE_COUNT]

Done.

https://codereview.chromium.org/11365174/diff/1/src/hydrogen.h#newcode382
src/hydrogen.h:382: TerminalNodeList *terminal_nodes_;
On 2012/11/14 15:28:18, danno wrote:
> I think "Terminal" might not be the right to use. I think something like
> "pre_transitioned_values_" might be better.

Done.

https://codereview.chromium.org/11365174/diff/1/src/hydrogen.h#newcode1014
src/hydrogen.h:1014: 
On 2012/11/14 15:28:18, danno wrote:
> nit: extra whitespace :-)

Done.

https://codereview.chromium.org/11365174/diff/1/src/hydrogen.h#newcode1300
src/hydrogen.h:1300: HCheckMaps** checkmap_instr=NULL);
On 2012/11/14 15:28:18, danno wrote:
> extra <sp> around =

Done.

https://codereview.chromium.org/11365174/diff/1/src/objects.cc
File src/objects.cc (right):

https://codereview.chromium.org/11365174/diff/1/src/objects.cc#newcode2340
src/objects.cc:2340: MaybeObject* AddMissingElementsTransitions(Map* map,
ElementsKind to_kind) {
On 2012/11/14 15:28:18, danno wrote:
> Perhaps it is time to move this to be part of the Map class' interface?

Done.

[mvstanton, 2012-11-27 16:17:28]

Hi all,
This is for Danno, who wanted to see the "fixed point iteration" algorithm that
replaces the weird stuff I did before. I plugged this in today. The decision
making part is done, what is missing is:

1) actually placing the hydrogen instructions (it'll be the same kind of surgery
I was doing before, I just didn't have time today to integrate that).
2) CheckMaps instructions are being ignored right now. This will be handled
along with 1) tomorrow.

It's enough to just look at the method HGraph::InsertElementsTransitions() right
now. There is the graph up and down propagation.

Thanks,
--Michael

[mvstanton, 2012-11-28 05:30:15]

Restored moving transition instructions, updating map checks with the new fixed
point iteration algorithm.

[danno, 2012-11-28 14:42:10]

Totally going in the right direction. Ignore all my comments except for the ones
on the latest version, which are still mostly high-level.

https://chromiumcodereview.appspot.com/11365174/diff/16002/src/elements-kind.h
File src/elements-kind.h (right):

https://chromiumcodereview.appspot.com/11365174/diff/16002/src/elements-kind....
src/elements-kind.h:218: ElementsKind GetUnifiedFastElementsKind(ElementsKind
kind1, ElementsKind kind2);
GetMostGeneralFastElementsKind?

https://chromiumcodereview.appspot.com/11365174/diff/16002/src/hydrogen-instr...
File src/hydrogen-instructions.h (right):

https://chromiumcodereview.appspot.com/11365174/diff/16002/src/hydrogen-instr...
src/hydrogen-instructions.h:4356: initialized_ = !defer_initialization;
Make this transparent with a single macro in ArrayInterface? e.g like in CL
10701054 AstVisitor in ast.h

https://chromiumcodereview.appspot.com/11365174/diff/16002/src/hydrogen-instr...
src/hydrogen-instructions.h:4412: void
PerformDeferredInitialization(ElementsKind new_elements_kind) {
Put this in the .cc

https://chromiumcodereview.appspot.com/11365174/diff/16002/src/hydrogen-instr...
src/hydrogen-instructions.h:4661: bool defer_initialization = false)
can you not have to care whether this is deferred, i.e. always to initialization
in a deferred way and visit the "bookmark" sites later?

https://chromiumcodereview.appspot.com/11365174/diff/16002/src/hydrogen.cc
File src/hydrogen.cc (right):

https://chromiumcodereview.appspot.com/11365174/diff/16002/src/hydrogen.cc#ne...
src/hydrogen.cc:2743: if (!use->block()->IsStartBlock()) {
More comments?

https://chromiumcodereview.appspot.com/11365174/diff/16002/src/hydrogen.cc#ne...
src/hydrogen.cc:3043: group->ComputeTransitionInputValues(GetMaximumValueID());
As discussed, this algorithm costs O(n x m), where n is number of loads/stores
and m is number of involved phi nodes + input values. Is there a way to
transform this to just visit phi nodes + input values once? and then propagate
to the load/stores, for a total expense of O(n + m)

https://chromiumcodereview.appspot.com/11365174/diff/16002/src/hydrogen.cc#ne...
src/hydrogen.cc:3095: MarkedTransitionElementsGroup* group =
marked_transitions_.at(i);
Is this just an ArrayInterface?

https://chromiumcodereview.appspot.com/11365174/diff/16002/src/hydrogen.cc#ne...
src/hydrogen.cc:10558: elements = HStoreKeyed::cast(instruction)->elements();
Can you add elements to ArrayInterface?

https://chromiumcodereview.appspot.com/11365174/diff/16002/src/hydrogen.cc#ne...
src/hydrogen.cc:10570: BitVector visited(maximumGraphValueID, zone());
maximum_graph_value_id

https://chromiumcodereview.appspot.com/11365174/diff/16002/src/hydrogen.h
File src/hydrogen.h (right):

https://chromiumcodereview.appspot.com/11365174/diff/16002/src/hydrogen.h#new...
src/hydrogen.h:246: class MarkedTransitionElementsGroup;
Marked has a meaning in the GC space, "bookmarked" would be better.

https://chromiumcodereview.appspot.com/11365174/diff/11016/src/hydrogen.cc
File src/hydrogen.cc (right):

https://chromiumcodereview.appspot.com/11365174/diff/11016/src/hydrogen.cc#ne...
src/hydrogen.cc:2457: class MapHandleMap BASE_EMBEDDED {
How about this idea. Just have a single table that maps {Map*, ElementsKind} ->
Handle<Map>. 

If you want the handle for the map itself, you add
{map, elements()->kind()} -> the map's handle
to the table.
If you want the "transitioned from family", you add 
{family_map, transitioned_kind} -> the transitioned_kind's handle
to the table. 

Probably reduces the code by about half. Then better name might be
TransitionedMapHandlesMap.

https://chromiumcodereview.appspot.com/11365174/diff/11016/src/hydrogen.cc#ne...
src/hydrogen.cc:2487: void Populate(ArrayInstruction* instruction) {
I kind of think that the methods to handle ArrayInstructions (this one and Add)
should logically live outside this class, since it would be great if the
MapHandleMap class only needs to know about the implementation of types it
directly contains.

https://chromiumcodereview.appspot.com/11365174/diff/11016/src/hydrogen.cc#ne...
src/hydrogen.cc:2530: MapHandleTable::Iterator i =
map_.find(*(handle->location()), true,
here and below: doesn't *handle return a Map°, you don't have to do
*(handle->location().

https://chromiumcodereview.appspot.com/11365174/diff/11016/src/hydrogen.cc#ne...
src/hydrogen.cc:2580: if (addafter == NULL) {
add_after

https://chromiumcodereview.appspot.com/11365174/diff/11016/src/hydrogen.cc#ne...
src/hydrogen.cc:2611: if (use != HValue::cast(transition)) {
Wow. How can this happen? Don't you just visit each use once, and since the
transition is brand new, when would they ever be equal?

https://chromiumcodereview.appspot.com/11365174/diff/11016/src/hydrogen.cc#ne...
src/hydrogen.cc:2626: if (!use->block()->IsStartBlock()) {
You mentioned that you copied this magic from somewhere else. Any chance that
you could pack that in a shared method that gets called from both sites?

https://chromiumcodereview.appspot.com/11365174/diff/11016/src/hydrogen.cc#ne...
src/hydrogen.cc:2710: Map* unified_map =
to()->LookupElementsTransitionMap(unified_elements_kind);
This won't be GC-safe if we're running concurrent compilation. you'll have to
use the MapHandleMap in some way.

https://chromiumcodereview.appspot.com/11365174/diff/11016/src/hydrogen.cc#ne...
src/hydrogen.cc:2711: Map* unified_from_value_map =
from_value->to()->LookupElementsTransitionMap(unified_elements_kind);
Same here.

https://chromiumcodereview.appspot.com/11365174/diff/11016/src/hydrogen.cc#ne...
src/hydrogen.cc:2733: Map* to_;
Can these be Handles?

https://chromiumcodereview.appspot.com/11365174/diff/11016/src/hydrogen.cc#ne...
src/hydrogen.cc:2812: void
HoistTransitionsFromArrayInstructionSites(ArrayInstruction* load_or_store,
If you make all of these methods inside of a HInsertElementsTransitions
optimization phase, then you probably can avoid passing MapHandleMap* and Zone*

https://chromiumcodereview.appspot.com/11365174/diff/11016/src/hydrogen.cc#ne...
src/hydrogen.cc:2824: }
if (load_or_store->bookmarks() == 0) return;

avoid the loop if there are no bookmarks.

https://chromiumcodereview.appspot.com/11365174/diff/11016/src/hydrogen.cc#ne...
src/hydrogen.cc:2929: // Walk the graph looking for store and load keyed
instructions.
I think it would be better if you build the list of ArrayInstructions explicitly
from HKeyedLoad/HKeyedStore's constructors, avoiding iterating over all
instructions.

https://chromiumcodereview.appspot.com/11365174/diff/11016/src/hydrogen.cc#ne...
src/hydrogen.cc:2983: // Now propagate information back down to input sites,
starting from root
root... do you mean transition input candidates?

https://chromiumcodereview.appspot.com/11365174/diff/11016/src/hydrogen.cc#ne...
src/hydrogen.cc:2989: if (!current_value->IsPhi() &&
!current_value->IsLoadKeyed() &&
Would things get easier if you had a up_worklist and a down_worklist? That way
you could initialize the down_worklist when you found roots during the
up_worklist iteration, avoiding having to go hunting for them in the table in a
separate step.

https://chromiumcodereview.appspot.com/11365174/diff/11016/src/hydrogen.cc#ne...
src/hydrogen.cc:3008: worklist.Add(WorkItem(current_value, value,
current_value), zone());
Is it wrong to call UpdateMapCheck here directly?

https://chromiumcodereview.appspot.com/11365174/diff/11016/src/hydrogen.cc#ne...
src/hydrogen.cc:3050: if (to_value->to() != NULL) {
Can you move this and the Finalize in the NULL case into
HoistTransitionsFromArrayInstructionSites, which maybe could be be just just
called PlaceArrayInstructionTransitions

https://chromiumcodereview.appspot.com/11365174/diff/11026/src/hydrogen-instr...
File src/hydrogen-instructions.h (right):

https://chromiumcodereview.appspot.com/11365174/diff/11026/src/hydrogen-instr...
src/hydrogen-instructions.h:4346: Handle<Map>* from_pointer() { return &from_; }
I don't think you need this version. Creating a Handle from another handle
doesn't allocate a new location_. So you should always be able to just pass
Handle<Map> around, even when you need to create another Handle<Map> based on
it.

https://chromiumcodereview.appspot.com/11365174/diff/11026/src/hydrogen-instr...
src/hydrogen-instructions.h:4359: *family() == *(other.family());
family must be equal if from and to are equal. You could probably make that part
some sort of assert instead.

https://chromiumcodereview.appspot.com/11365174/diff/11026/src/hydrogen-instr...
src/hydrogen-instructions.h:4363: HTransitionElementsKind* transition_;
Here's a radical idea. Since you need to allocate one of these for every
HTransitionElementsKind, why not just add all this functionality to
HTransitionElementsKind itself? You could remove the from_ and to_, since they
are already recorded in the TransitionElementsKind instruction.

https://chromiumcodereview.appspot.com/11365174/diff/11026/src/hydrogen-instr...
src/hydrogen-instructions.h:4371: class ArrayInstruction: public
HTemplateInstruction<3> {
Maybe HArrayInstruction, it's more consistent.

https://chromiumcodereview.appspot.com/11365174/diff/11026/src/hydrogen-instr...
src/hydrogen-instructions.h:4375: bookmarks_(new(zone)
ZoneList<TransitionElementsBookmark>(10, zone)),
Maybe TransitionElementsBookmark*, and allocate the bookmarks from the zone when
they're added. Also, 10 seems like a lot, might cause a lot of extra space to be
allocated that is never used.

https://chromiumcodereview.appspot.com/11365174/diff/11026/src/hydrogen-instr...
src/hydrogen-instructions.h:4410: // ElementsKind elements_kind =
most_general_map()->elements_kind();
Is this comment stale?

[mvstanton, 2012-12-04 11:39:58]

Hi guys,
Remaining work:
1) ResolutionTableValue::to_ Map* could be a handle
2) New unit test needs work
3) I'm not sure how to characterize performance at this point. Now that I've
addressed "low hanging fruit" (deopts) any gains appear to be lost in noise...

https://chromiumcodereview.appspot.com/11365174/diff/16002/src/hydrogen-instr...
File src/hydrogen-instructions.h (right):

https://chromiumcodereview.appspot.com/11365174/diff/16002/src/hydrogen-instr...
src/hydrogen-instructions.h:4356: initialized_ = !defer_initialization;
On 2012/11/28 14:42:10, danno wrote:
> Make this transparent with a single macro in ArrayInterface? e.g like in CL
> 10701054 AstVisitor in ast.h

Done.

https://chromiumcodereview.appspot.com/11365174/diff/16002/src/hydrogen-instr...
src/hydrogen-instructions.h:4412: void
PerformDeferredInitialization(ElementsKind new_elements_kind) {
On 2012/11/28 14:42:10, danno wrote:
> Put this in the .cc

Done.

https://chromiumcodereview.appspot.com/11365174/diff/16002/src/hydrogen-instr...
src/hydrogen-instructions.h:4661: bool defer_initialization = false)
On 2012/11/28 14:42:10, danno wrote:
> can you not have to care whether this is deferred, i.e. always to
initialization
> in a deferred way and visit the "bookmark" sites later?

That didn't work because there are protections around several of the flags that
prevent them being set more than once. I figured I should respect that. Though I
did make things a bit cleaner with HArrayInstruction, I think.

https://chromiumcodereview.appspot.com/11365174/diff/11016/src/hydrogen.cc
File src/hydrogen.cc (right):

https://chromiumcodereview.appspot.com/11365174/diff/11016/src/hydrogen.cc#ne...
src/hydrogen.cc:2457: class MapHandleMap BASE_EMBEDDED {
On 2012/11/28 14:42:10, danno wrote:
> How about this idea. Just have a single table that maps {Map*, ElementsKind}
->
> Handle<Map>. 
> 
> If you want the handle for the map itself, you add
> {map, elements()->kind()} -> the map's handle
> to the table.
> If you want the "transitioned from family", you add 
> {family_map, transitioned_kind} -> the transitioned_kind's handle
> to the table. 
> 
> Probably reduces the code by about half. Then better name might be
> TransitionedMapHandlesMap. 

Done.

https://chromiumcodereview.appspot.com/11365174/diff/11016/src/hydrogen.cc#ne...
src/hydrogen.cc:2487: void Populate(ArrayInstruction* instruction) {
On 2012/11/28 14:42:10, danno wrote:
> I kind of think that the methods to handle ArrayInstructions (this one and
Add)
> should logically live outside this class, since it would be great if the
> MapHandleMap class only needs to know about the implementation of types it
> directly contains.

Done.

https://chromiumcodereview.appspot.com/11365174/diff/11016/src/hydrogen.cc#ne...
src/hydrogen.cc:2530: MapHandleTable::Iterator i =
map_.find(*(handle->location()), true,
On 2012/11/28 14:42:10, danno wrote:
> here and below: doesn't *handle return a Map°, you don't have to do
> *(handle->location().

Done.

https://chromiumcodereview.appspot.com/11365174/diff/11016/src/hydrogen.cc#ne...
src/hydrogen.cc:2580: if (addafter == NULL) {
On 2012/11/28 14:42:10, danno wrote:
> add_after

Done.

https://chromiumcodereview.appspot.com/11365174/diff/11016/src/hydrogen.cc#ne...
src/hydrogen.cc:2611: if (use != HValue::cast(transition)) {
On 2012/11/28 14:42:10, danno wrote:
> Wow. How can this happen? Don't you just visit each use once, and since the
> transition is brand new, when would they ever be equal?

Note that the iterator starts at last_in_chain_->uses(), not
transition_input_->uses(), so indeed, our newly added HTransitionElementsKind is
going to be a usage. Ugh!

https://chromiumcodereview.appspot.com/11365174/diff/11016/src/hydrogen.cc#ne...
src/hydrogen.cc:2626: if (!use->block()->IsStartBlock()) {
On 2012/11/28 14:42:10, danno wrote:
> You mentioned that you copied this magic from somewhere else. Any chance that
> you could pack that in a shared method that gets called from both sites?

Done.

https://chromiumcodereview.appspot.com/11365174/diff/11016/src/hydrogen.cc#ne...
src/hydrogen.cc:2710: Map* unified_map =
to()->LookupElementsTransitionMap(unified_elements_kind);
On 2012/11/28 14:42:10, danno wrote:
> This won't be GC-safe if we're running concurrent compilation. you'll have to
> use the MapHandleMap in some way.

Done.

https://chromiumcodereview.appspot.com/11365174/diff/11016/src/hydrogen.cc#ne...
src/hydrogen.cc:2711: Map* unified_from_value_map =
from_value->to()->LookupElementsTransitionMap(unified_elements_kind);
On 2012/11/28 14:42:10, danno wrote:
> Same here.

Done.

https://chromiumcodereview.appspot.com/11365174/diff/11016/src/hydrogen.cc#ne...
src/hydrogen.cc:2812: void
HoistTransitionsFromArrayInstructionSites(ArrayInstruction* load_or_store,
On 2012/11/28 14:42:10, danno wrote:
> If you make all of these methods inside of a HInsertElementsTransitions
> optimization phase, then you probably can avoid passing MapHandleMap* and
Zone*

I solved it a little differently, moving the method as a member of new class
HTransitionHoister.

https://chromiumcodereview.appspot.com/11365174/diff/11016/src/hydrogen.cc#ne...
src/hydrogen.cc:2824: }
On 2012/11/28 14:42:10, danno wrote:
> if (load_or_store->bookmarks() == 0) return;
> 
> avoid the loop if there are no bookmarks.

Done.

https://chromiumcodereview.appspot.com/11365174/diff/11016/src/hydrogen.cc#ne...
src/hydrogen.cc:2929: // Walk the graph looking for store and load keyed
instructions.
On 2012/11/28 14:42:10, danno wrote:
> I think it would be better if you build the list of ArrayInstructions
explicitly
> from HKeyedLoad/HKeyedStore's constructors, avoiding iterating over all
> instructions.

Done.

https://chromiumcodereview.appspot.com/11365174/diff/11016/src/hydrogen.cc#ne...
src/hydrogen.cc:2989: if (!current_value->IsPhi() &&
!current_value->IsLoadKeyed() &&
On 2012/11/28 14:42:10, danno wrote:
> Would things get easier if you had a up_worklist and a down_worklist? That way
> you could initialize the down_worklist when you found roots during the
> up_worklist iteration, avoiding having to go hunting for them in the table in
a
> separate step.

Done.

https://chromiumcodereview.appspot.com/11365174/diff/11016/src/hydrogen.cc#ne...
src/hydrogen.cc:3008: worklist.Add(WorkItem(current_value, value,
current_value), zone());
On 2012/11/28 14:42:10, danno wrote:
> Is it wrong to call UpdateMapCheck here directly?

We could get away with that. I was thinking though, that the logic around
calling UpdateMapCheck is a bit careful and I'd rather do all the "actual
operations" in one place.

https://chromiumcodereview.appspot.com/11365174/diff/11016/src/hydrogen.cc#ne...
src/hydrogen.cc:3050: if (to_value->to() != NULL) {
On 2012/11/28 14:42:10, danno wrote:
> Can you move this and the Finalize in the NULL case into
> HoistTransitionsFromArrayInstructionSites, which maybe could be be just just
> called PlaceArrayInstructionTransitions

Done.

https://chromiumcodereview.appspot.com/11365174/diff/11026/src/hydrogen-instr...
File src/hydrogen-instructions.h (right):

https://chromiumcodereview.appspot.com/11365174/diff/11026/src/hydrogen-instr...
src/hydrogen-instructions.h:4363: HTransitionElementsKind* transition_;
On 2012/11/28 14:42:10, danno wrote:
> Here's a radical idea. Since you need to allocate one of these for every
> HTransitionElementsKind, why not just add all this functionality to
> HTransitionElementsKind itself? You could remove the from_ and to_, since they
> are already recorded in the TransitionElementsKind instruction. 

Done.

https://chromiumcodereview.appspot.com/11365174/diff/11026/src/hydrogen-instr...
src/hydrogen-instructions.h:4371: class ArrayInstruction: public
HTemplateInstruction<3> {
On 2012/11/28 14:42:10, danno wrote:
> Maybe HArrayInstruction, it's more consistent.

Done.

https://chromiumcodereview.appspot.com/11365174/diff/11026/src/hydrogen-instr...
src/hydrogen-instructions.h:4375: bookmarks_(new(zone)
ZoneList<TransitionElementsBookmark>(10, zone)),
On 2012/11/28 14:42:10, danno wrote:
> Maybe TransitionElementsBookmark*, and allocate the bookmarks from the zone
when
> they're added. Also, 10 seems like a lot, might cause a lot of extra space to
be
> allocated that is never used.

Got rid of the Bookmarks entirely.

https://chromiumcodereview.appspot.com/11365174/diff/11026/src/hydrogen-instr...
src/hydrogen-instructions.h:4410: // ElementsKind elements_kind =
most_general_map()->elements_kind();
On 2012/11/28 14:42:10, danno wrote:
> Is this comment stale?

Done.