Support for multiple register values

Support for multiple register values

- Adds a PairLocation type (Location is still a single word but now has two tags one for constants and one for pairs).
- New representations: kPairOfTagged & kPairOfUnboxedDouble.
- Register allocator uses second SSA index for Definitions that use two registers.
- Fix LiveRange shape for kWritableRegister inputs.
- Updated MergedMathInstr that returns a kPairOfTagged or kPairOfUnboxedDouble (depending on the merged math kind).
- A new instruction (ExtractNthOutput) for extracting a single register from an instruction that has a output register pair.

Open issues that need to be addressed in a follow up CL:

- Adjust PhiInstr and handling of PhiInstr in the register allocator to work with output pairs (once unboxed mints are in GPRs).

R=fschneider@google.com, srdjan@google.com

Committed: https://code.google.com/p/dart/source/detail?r=34833

[Cutch, 2014-04-03 17:26:27]

PTAL

[Vyacheslav Egorov (Google), 2014-04-03 18:10:08]

overall I think we are moving in the right direction with this CL. I am still
concerned that memory usage will go up for all instructions even those that use
1 single SSA index. We should really attempt to grandfather it into the system
without penalizing the most common case.

https://codereview.chromium.org/215363004/diff/120001/runtime/vm/flow_graph.cc
File runtime/vm/flow_graph.cc (right):

https://codereview.chromium.org/215363004/diff/120001/runtime/vm/flow_graph.c...
runtime/vm/flow_graph.cc:121: defn->set_ssa_temp_index2(alloc_ssa_temp_index());
I am not sure I like the naming here.

https://codereview.chromium.org/215363004/diff/120001/runtime/vm/flow_graph.c...
runtime/vm/flow_graph.cc:138: if (defn->RequiresTwoSSATempIndexes()) {
The code is duplicated in multiple places. I wonder if we can just shift it into
a separate function.

AssignSSATempIndex(instr);

https://codereview.chromium.org/215363004/diff/120001/runtime/vm/intermediate...
File runtime/vm/intermediate_language.h (right):

https://codereview.chromium.org/215363004/diff/120001/runtime/vm/intermediate...
runtime/vm/intermediate_language.h:1909: intptr_t ssa_temp_index2_;
Can we sink it down into instructions that actually use it, making setters and
getters virtual?

[Cutch, 2014-04-03 18:35:06]

https://codereview.chromium.org/215363004/diff/120001/runtime/vm/flow_graph.cc
File runtime/vm/flow_graph.cc (right):

https://codereview.chromium.org/215363004/diff/120001/runtime/vm/flow_graph.c...
runtime/vm/flow_graph.cc:121: defn->set_ssa_temp_index2(alloc_ssa_temp_index());
On 2014/04/03 18:10:09, Vyacheslav Egorov (Google) wrote:
> I am not sure I like the naming here.

I've renamed it to pair_ssa_index. I don't really like either name.

virtual bool RequiresPairSSAIndex() const;
virtual intptr_t pair_ssa_index() const;
virtual void set_pair_ssa_index(intptr_t idx);

https://codereview.chromium.org/215363004/diff/120001/runtime/vm/flow_graph.c...
runtime/vm/flow_graph.cc:138: if (defn->RequiresTwoSSATempIndexes()) {
On 2014/04/03 18:10:09, Vyacheslav Egorov (Google) wrote:
> The code is duplicated in multiple places. I wonder if we can just shift it
into
> a separate function.
> 
> AssignSSATempIndex(instr);

Done. Added the following to FlowGraph:

void AssignSSAIndexes(Definition* def);

https://codereview.chromium.org/215363004/diff/120001/runtime/vm/intermediate...
File runtime/vm/intermediate_language.h (right):

https://codereview.chromium.org/215363004/diff/120001/runtime/vm/intermediate...
runtime/vm/intermediate_language.h:1909: intptr_t ssa_temp_index2_;
On 2014/04/03 18:10:09, Vyacheslav Egorov (Google) wrote:
> Can we sink it down into instructions that actually use it, making setters and
> getters virtual?

Done.

[srdjan, 2014-04-03 20:51:28]

Early DBCs

https://codereview.chromium.org/215363004/diff/140001/runtime/vm/flow_graph.h
File runtime/vm/flow_graph.h (right):

https://codereview.chromium.org/215363004/diff/140001/runtime/vm/flow_graph.h...
runtime/vm/flow_graph.h:123: void AssignSSAIndexes(Definition* def) {
Optional: Why not name AllocateSSAIndexes?

https://codereview.chromium.org/215363004/diff/140001/runtime/vm/flow_graph_a...
File runtime/vm/flow_graph_allocator.cc (right):

https://codereview.chromium.org/215363004/diff/140001/runtime/vm/flow_graph_a...
runtime/vm/flow_graph_allocator.cc:880: ASSERT(in_ref);
Use explicit test in_ref != NULL, here and below.

https://codereview.chromium.org/215363004/diff/140001/runtime/vm/flow_graph_a...
File runtime/vm/flow_graph_allocator.h (right):

https://codereview.chromium.org/215363004/diff/140001/runtime/vm/flow_graph_a...
runtime/vm/flow_graph_allocator.h:127: BitVector* interference_set);
Humongous argument list. Maybe split it up.

[Cutch, 2014-04-03 22:05:36]

https://codereview.chromium.org/215363004/diff/140001/runtime/vm/flow_graph.h
File runtime/vm/flow_graph.h (right):

https://codereview.chromium.org/215363004/diff/140001/runtime/vm/flow_graph.h...
runtime/vm/flow_graph.h:123: void AssignSSAIndexes(Definition* def) {
On 2014/04/03 20:51:29, srdjan wrote:
> Optional: Why not name AllocateSSAIndexes?

Done.

https://codereview.chromium.org/215363004/diff/140001/runtime/vm/flow_graph_a...
File runtime/vm/flow_graph_allocator.cc (right):

https://codereview.chromium.org/215363004/diff/140001/runtime/vm/flow_graph_a...
runtime/vm/flow_graph_allocator.cc:880: ASSERT(in_ref);
On 2014/04/03 20:51:29, srdjan wrote:
> Use explicit test in_ref != NULL, here and below.

Done.

https://codereview.chromium.org/215363004/diff/140001/runtime/vm/flow_graph_a...
File runtime/vm/flow_graph_allocator.h (right):

https://codereview.chromium.org/215363004/diff/140001/runtime/vm/flow_graph_a...
runtime/vm/flow_graph_allocator.h:127: BitVector* interference_set);
On 2014/04/03 20:51:29, srdjan wrote:
> Humongous argument list. Maybe split it up.

I'd like to keep all of the logic for processing an output in one function. I
could create a structure for passing the arguments?

[Florian Schneider, 2014-04-04 11:52:46]

https://codereview.chromium.org/215363004/diff/160001/runtime/vm/flow_graph_a...
File runtime/vm/flow_graph_allocator.cc (right):

https://codereview.chromium.org/215363004/diff/160001/runtime/vm/flow_graph_a...
runtime/vm/flow_graph_allocator.cc:1131: 
No need for extra \n.

https://codereview.chromium.org/215363004/diff/160001/runtime/vm/flow_graph_a...
runtime/vm/flow_graph_allocator.cc:2484: LiveRange* parent =
GetLiveRange(range->vreg());
Unintended change?

https://codereview.chromium.org/215363004/diff/160001/runtime/vm/flow_graph_a...
runtime/vm/flow_graph_allocator.cc:2630: if (def->RequiresPairSSAIndex()) {
Can the initial_definitions of the GraphEntry ever require a pair? I don't think
so. Maybe add an ASSERT instead.

https://codereview.chromium.org/215363004/diff/160001/runtime/vm/flow_graph_t...
File runtime/vm/flow_graph_type_propagator.cc (right):

https://codereview.chromium.org/215363004/diff/160001/runtime/vm/flow_graph_t...
runtime/vm/flow_graph_type_propagator.cc:1316: return
CompileType::FromCid(kSmiCid);
This relies on the the instruction where the output is extracted from, so I
don't think the smi-type should be hard-coded here.

https://codereview.chromium.org/215363004/diff/160001/runtime/vm/intermediate...
File runtime/vm/intermediate_language.cc (right):

https://codereview.chromium.org/215363004/diff/160001/runtime/vm/intermediate...
runtime/vm/intermediate_language.cc:3225: : inputs_(inputs),
pair_ssa_index_ is uninitialized.

https://codereview.chromium.org/215363004/diff/160001/runtime/vm/intermediate...
File runtime/vm/intermediate_language_ia32.cc (right):

https://codereview.chromium.org/215363004/diff/160001/runtime/vm/intermediate...
runtime/vm/intermediate_language_ia32.cc:5046: if (kind() ==
MergedMathInstr::kSinCos) {
I wonder how much code is actually shared between SinCos and DivMod. I think
it's too little (only little boilerplate in intermediate_language.h) to have one
class for both. I'd split them up -  maybe inherit from a common
MergedInstruction super-class if at all.

https://codereview.chromium.org/215363004/diff/160001/runtime/vm/locations.h
File runtime/vm/locations.h (right):

https://codereview.chromium.org/215363004/diff/160001/runtime/vm/locations.h#...
runtime/vm/locations.h:62: // the same as kConstant or kPairLocation.
Maybe you can turn this comment into COMPILE_ASSERT. This would prevent mistakes
if someone does not read this comment in the future.

https://codereview.chromium.org/215363004/diff/160001/runtime/vm/locations.h#...
runtime/vm/locations.h:130: ASSERT((kPairLocation & kConstantMask) ==
kPairLocation);
Use COMPILE_ASSERT here.

https://codereview.chromium.org/215363004/diff/160001/runtime/vm/locations.h#...
runtime/vm/locations.h:131: return (value_ & kConstantMask) == kPairLocation;
kConstantMask is not the right name anymore since it is used for constants and
pairs now. Maybe rename to kConstantOrPairMask or just kTagMask?

[Cutch, 2014-04-04 16:34:45]

https://codereview.chromium.org/215363004/diff/160001/runtime/vm/flow_graph_a...
File runtime/vm/flow_graph_allocator.cc (right):

https://codereview.chromium.org/215363004/diff/160001/runtime/vm/flow_graph_a...
runtime/vm/flow_graph_allocator.cc:1131: 
On 2014/04/04 11:52:46, Florian Schneider wrote:
> No need for extra \n.

Done.

https://codereview.chromium.org/215363004/diff/160001/runtime/vm/flow_graph_a...
runtime/vm/flow_graph_allocator.cc:2484: LiveRange* parent =
GetLiveRange(range->vreg());
On 2014/04/04 11:52:46, Florian Schneider wrote:
> Unintended change?

Done.

https://codereview.chromium.org/215363004/diff/160001/runtime/vm/flow_graph_a...
runtime/vm/flow_graph_allocator.cc:2630: if (def->RequiresPairSSAIndex()) {
On 2014/04/04 11:52:46, Florian Schneider wrote:
> Can the initial_definitions of the GraphEntry ever require a pair? I don't
think
> so. Maybe add an ASSERT instead.

Done.

https://codereview.chromium.org/215363004/diff/160001/runtime/vm/flow_graph_t...
File runtime/vm/flow_graph_type_propagator.cc (right):

https://codereview.chromium.org/215363004/diff/160001/runtime/vm/flow_graph_t...
runtime/vm/flow_graph_type_propagator.cc:1316: return
CompileType::FromCid(kSmiCid);
On 2014/04/04 11:52:46, Florian Schneider wrote:
> This relies on the the instruction where the output is extracted from, so I
> don't think the smi-type should be hard-coded here.

Done.

https://codereview.chromium.org/215363004/diff/160001/runtime/vm/intermediate...
File runtime/vm/intermediate_language.cc (right):

https://codereview.chromium.org/215363004/diff/160001/runtime/vm/intermediate...
runtime/vm/intermediate_language.cc:3225: : inputs_(inputs),
On 2014/04/04 11:52:46, Florian Schneider wrote:
> pair_ssa_index_ is uninitialized.

Done.

https://codereview.chromium.org/215363004/diff/160001/runtime/vm/intermediate...
File runtime/vm/intermediate_language_ia32.cc (right):

https://codereview.chromium.org/215363004/diff/160001/runtime/vm/intermediate...
runtime/vm/intermediate_language_ia32.cc:5046: if (kind() ==
MergedMathInstr::kSinCos) {
On 2014/04/04 11:52:46, Florian Schneider wrote:
> I wonder how much code is actually shared between SinCos and DivMod. I think
> it's too little (only little boilerplate in intermediate_language.h) to have
one
> class for both. I'd split them up -  maybe inherit from a common
> MergedInstruction super-class if at all.

Note that this is a clone of MergedMathInstr that will go away before I land it.
I'd rather cleanup MergedMathInstr in a separate CL.

https://codereview.chromium.org/215363004/diff/160001/runtime/vm/locations.h
File runtime/vm/locations.h (right):

https://codereview.chromium.org/215363004/diff/160001/runtime/vm/locations.h#...
runtime/vm/locations.h:62: // the same as kConstant or kPairLocation.
On 2014/04/04 11:52:46, Florian Schneider wrote:
> Maybe you can turn this comment into COMPILE_ASSERT. This would prevent
mistakes
> if someone does not read this comment in the future.

Done.

https://codereview.chromium.org/215363004/diff/160001/runtime/vm/locations.h#...
runtime/vm/locations.h:130: ASSERT((kPairLocation & kConstantMask) ==
kPairLocation);
On 2014/04/04 11:52:46, Florian Schneider wrote:
> Use COMPILE_ASSERT here.

Done here and elsewhere.

https://codereview.chromium.org/215363004/diff/160001/runtime/vm/locations.h#...
runtime/vm/locations.h:131: return (value_ & kConstantMask) == kPairLocation;
On 2014/04/04 11:52:46, Florian Schneider wrote:
> kConstantMask is not the right name anymore since it is used for constants and
> pairs now. Maybe rename to kConstantOrPairMask or just kTagMask?

Renamed to kLocationTagMask.

[Cutch, 2014-04-07 17:55:31]

I'm done all pending work and this is waiting on review. PTAL.

[srdjan, 2014-04-07 18:22:50]

LGTM after fixing the printing of pairs.

https://codereview.chromium.org/215363004/diff/220001/runtime/vm/flow_graph.cc
File runtime/vm/flow_graph.cc (right):

https://codereview.chromium.org/215363004/diff/220001/runtime/vm/flow_graph.c...
runtime/vm/flow_graph.cc:119: AllocateSSAIndexes(defn);
AllocateSSAIndexes(instr->AsDefinition()) .. also below ?

https://codereview.chromium.org/215363004/diff/220001/runtime/vm/flow_graph.h
File runtime/vm/flow_graph.h (right):

https://codereview.chromium.org/215363004/diff/220001/runtime/vm/flow_graph.h...
runtime/vm/flow_graph.h:126: // Always allocate a second index. This index
unused except
add a verb, e.g., 'is' ?

https://codereview.chromium.org/215363004/diff/220001/runtime/vm/flow_graph_a...
File runtime/vm/flow_graph_allocator.cc (right):

https://codereview.chromium.org/215363004/diff/220001/runtime/vm/flow_graph_a...
runtime/vm/flow_graph_allocator.cc:826: if (def->HasPairRepresentation()) {
Maybe you can add comment somewhere that not both pairs have the same liveness
range.

https://codereview.chromium.org/215363004/diff/220001/runtime/vm/flow_graph_a...
runtime/vm/flow_graph_allocator.cc:1239: true,
Add comments what true, NULL, -1 arguments mean.

[Florian Schneider, 2014-04-08 09:48:44]

LGTM.

https://codereview.chromium.org/215363004/diff/220001/runtime/vm/flow_graph_a...
File runtime/vm/flow_graph_allocator.cc (right):

https://codereview.chromium.org/215363004/diff/220001/runtime/vm/flow_graph_a...
runtime/vm/flow_graph_allocator.cc:131: current_def->ssa_temp_index() +
kPairVirtualRegisterOffset);
Maybe just add a helper

ToSecondPairIndex(current_def->ssa_temp_index())

https://codereview.chromium.org/215363004/diff/220001/runtime/vm/intermediate...
File runtime/vm/intermediate_language_ia32.cc (right):

https://codereview.chromium.org/215363004/diff/220001/runtime/vm/intermediate...
runtime/vm/intermediate_language_ia32.cc:4906: summary->set_out(0,
Location::Pair(Location::RequiresRegister(),
How about making the output a pair EDX:EAX instead? Then you don't need EDX as a
temp?

https://codereview.chromium.org/215363004/diff/220001/runtime/vm/intermediate...
File runtime/vm/intermediate_language_x64.cc (right):

https://codereview.chromium.org/215363004/diff/220001/runtime/vm/intermediate...
runtime/vm/intermediate_language_x64.cc:4813: summary->set_out(0,
Location::Pair(Location::RequiresRegister(),
Same here: It should be possible to have the output in RDX:RAX.

[Cutch, 2014-04-08 15:56:15]

https://codereview.chromium.org/215363004/diff/220001/runtime/vm/flow_graph.cc
File runtime/vm/flow_graph.cc (right):

https://codereview.chromium.org/215363004/diff/220001/runtime/vm/flow_graph.c...
runtime/vm/flow_graph.cc:119: AllocateSSAIndexes(defn);
On 2014/04/07 18:22:50, srdjan wrote:
> AllocateSSAIndexes(instr->AsDefinition()) .. also below ?

Done here and elsewhere.

https://codereview.chromium.org/215363004/diff/220001/runtime/vm/flow_graph.h
File runtime/vm/flow_graph.h (right):

https://codereview.chromium.org/215363004/diff/220001/runtime/vm/flow_graph.h...
runtime/vm/flow_graph.h:126: // Always allocate a second index. This index
unused except
On 2014/04/07 18:22:50, srdjan wrote:
> add a verb, e.g., 'is' ?

Done.

https://codereview.chromium.org/215363004/diff/220001/runtime/vm/flow_graph_a...
File runtime/vm/flow_graph_allocator.cc (right):

https://codereview.chromium.org/215363004/diff/220001/runtime/vm/flow_graph_a...
runtime/vm/flow_graph_allocator.cc:131: current_def->ssa_temp_index() +
kPairVirtualRegisterOffset);
On 2014/04/08 09:48:45, Florian Schneider wrote:
> Maybe just add a helper
> 
> ToSecondPairIndex(current_def->ssa_temp_index())
> 

Done.

https://codereview.chromium.org/215363004/diff/220001/runtime/vm/flow_graph_a...
runtime/vm/flow_graph_allocator.cc:826: if (def->HasPairRepresentation()) {
On 2014/04/07 18:22:50, srdjan wrote:
> Maybe you can add comment somewhere that not both pairs have the same liveness
> range.

Done.

https://codereview.chromium.org/215363004/diff/220001/runtime/vm/flow_graph_a...
runtime/vm/flow_graph_allocator.cc:1239: true,
On 2014/04/07 18:22:50, srdjan wrote:
> Add comments what true, NULL, -1 arguments mean.

Done.

https://codereview.chromium.org/215363004/diff/220001/runtime/vm/intermediate...
File runtime/vm/intermediate_language_ia32.cc (right):

https://codereview.chromium.org/215363004/diff/220001/runtime/vm/intermediate...
runtime/vm/intermediate_language_ia32.cc:4906: summary->set_out(0,
Location::Pair(Location::RequiresRegister(),
On 2014/04/08 09:48:45, Florian Schneider wrote:
> How about making the output a pair EDX:EAX instead? Then you don't need EDX as
a
> temp?

Done.

https://codereview.chromium.org/215363004/diff/220001/runtime/vm/intermediate...
File runtime/vm/intermediate_language_x64.cc (right):

https://codereview.chromium.org/215363004/diff/220001/runtime/vm/intermediate...
runtime/vm/intermediate_language_x64.cc:4813: summary->set_out(0,
Location::Pair(Location::RequiresRegister(),
On 2014/04/08 09:48:45, Florian Schneider wrote:
> Same here: It should be possible to have the output in RDX:RAX.

Done.

[Cutch, 2014-04-08 15:57:10]

Will land Patch Set 13. Flow graph printing is fixed.

[Cutch, 2014-04-08 16:13:56]

Committed patchset #13 manually as r34833 (presubmit successful).