[crankshaft] Fragmentation-free allocation folding.

[crankshaft] Fragmentation-free allocation folding.

The new allocation folding implementation avoids fragmentation between folded allocation. As a consequence, our heap will always be iterable i.e. we do not have to perform a garbage collection before iterating the heap.

BUG=chromium:580959
LOG=n

Committed: https://crrev.com/61f5fbbb1926e1ffb672214a043e8c98db0e8af6
Cr-Commit-Position: refs/heads/master@{#36133}

[Hannes Payer (out of office), 2016-04-19 07:09:47]

hpayer@chromium.org changed reviewers:
+ bmeurer@chromium.org

[Hannes Payer (out of office), 2016-04-19 07:09:47]

Hi Benedikt,
can you have a look? This CL just contains the x64 port for now.
Thanks!

[Hannes Payer (out of office), 2016-04-19 07:14:04]

Description was changed from

==========
[crankshaft] Fragmentation-free allocation folding.

BUG=chromium:580959
LOG=n
==========

to

==========
[crankshaft] Fragmentation-free allocation folding.

The new allocation folding implementation avoids fragmentation between folded
allocation. As a consequence, our heap will always be iterable i.e. we do not
have to perform a garbage collection before iterating the heap.

BUG=chromium:580959
LOG=n
==========

[Benedikt Meurer, 2016-04-19 07:25:39]

Looking good, first round of comments.

https://codereview.chromium.org/1899813003/diff/20001/src/crankshaft/hydrogen...
File src/crankshaft/hydrogen-instructions.h (right):

https://codereview.chromium.org/1899813003/diff/20001/src/crankshaft/hydrogen...
src/crankshaft/hydrogen-instructions.h:5046: ALLOCATION_FOLDING_DOMINATED = 1 <<
6
Is there a better name than "dominated"?

https://codereview.chromium.org/1899813003/diff/20001/src/x64/macro-assembler...
File src/x64/macro-assembler-x64.cc (right):

https://codereview.chromium.org/1899813003/diff/20001/src/x64/macro-assembler...
src/x64/macro-assembler-x64.cc:4901: if (!top_reg.is(result)) {
We can fuse this movp and the addp into a single leap for dominated allocations.

https://codereview.chromium.org/1899813003/diff/20001/src/x64/macro-assembler...
src/x64/macro-assembler-x64.cc:4908: // Calculate new top and bail out if new
space is exhausted.
This comment is wrong here, as the calculation happens in the addp above.

https://codereview.chromium.org/1899813003/diff/20001/src/x64/macro-assembler...
src/x64/macro-assembler-x64.cc:4979: if (!object_size.is(result_end)) {
Same here, see comment above.

https://codereview.chromium.org/1899813003/diff/20001/src/x64/macro-assembler...
src/x64/macro-assembler-x64.cc:4986: // Calculate new top and bail out if new
space is exhausted.
Same here, see comment above.

https://codereview.chromium.org/1899813003/diff/20001/src/x64/macro-assembler...
src/x64/macro-assembler-x64.cc:5009: subp(value, Immediate(kHeapObjectTag));
How about this one instead?

// TODO(hpayer): Change top and limit to tagged.
leap(kScratchRegister, Operand(value, -kHeapObjectTag));
Store(allocation_top, kScratchRegister);

[Michael Lippautz, 2016-04-19 10:49:50]

mlippautz@chromium.org changed reviewers:
+ mlippautz@chromium.org

[Michael Lippautz, 2016-04-19 10:49:50]

https://codereview.chromium.org/1899813003/diff/20001/src/heap/spaces.cc
File src/heap/spaces.cc (right):

https://codereview.chromium.org/1899813003/diff/20001/src/heap/spaces.cc#newc...
src/heap/spaces.cc:2393: } else if (bytes_left >= 0) {
nit: can we do this as "else" to make clear that this will always hold? (we
already have the DCHECK on line 2357 that enforces this)

[Hannes Payer (out of office), 2016-04-19 11:03:56]

https://codereview.chromium.org/1899813003/diff/20001/src/crankshaft/hydrogen...
File src/crankshaft/hydrogen-instructions.h (right):

https://codereview.chromium.org/1899813003/diff/20001/src/crankshaft/hydrogen...
src/crankshaft/hydrogen-instructions.h:5046: ALLOCATION_FOLDING_DOMINATED = 1 <<
6
On 2016/04/19 at 07:25:38, Benedikt Meurer wrote:
> Is there a better name than "dominated"?

Changed to ALLOCATION_FOLDED. Done.

https://codereview.chromium.org/1899813003/diff/20001/src/heap/spaces.cc
File src/heap/spaces.cc (right):

https://codereview.chromium.org/1899813003/diff/20001/src/heap/spaces.cc#newc...
src/heap/spaces.cc:2393: } else if (bytes_left >= 0) {
On 2016/04/19 at 10:49:50, Michael Lippautz wrote:
> nit: can we do this as "else" to make clear that this will always hold? (we
already have the DCHECK on line 2357 that enforces this)

Also would also mean that this value could be negative.

https://codereview.chromium.org/1899813003/diff/20001/src/x64/macro-assembler...
File src/x64/macro-assembler-x64.cc (right):

https://codereview.chromium.org/1899813003/diff/20001/src/x64/macro-assembler...
src/x64/macro-assembler-x64.cc:4901: if (!top_reg.is(result)) {
On 2016/04/19 at 07:25:39, Benedikt Meurer wrote:
> We can fuse this movp and the addp into a single leap for dominated
allocations.

Done.

https://codereview.chromium.org/1899813003/diff/20001/src/x64/macro-assembler...
src/x64/macro-assembler-x64.cc:4908: // Calculate new top and bail out if new
space is exhausted.
On 2016/04/19 at 07:25:39, Benedikt Meurer wrote:
> This comment is wrong here, as the calculation happens in the addp above.

Done.

https://codereview.chromium.org/1899813003/diff/20001/src/x64/macro-assembler...
src/x64/macro-assembler-x64.cc:4979: if (!object_size.is(result_end)) {
On 2016/04/19 at 07:25:38, Benedikt Meurer wrote:
> Same here, see comment above.

Done.

https://codereview.chromium.org/1899813003/diff/20001/src/x64/macro-assembler...
src/x64/macro-assembler-x64.cc:4986: // Calculate new top and bail out if new
space is exhausted.
On 2016/04/19 at 07:25:38, Benedikt Meurer wrote:
> Same here, see comment above.

Done.

https://codereview.chromium.org/1899813003/diff/20001/src/x64/macro-assembler...
src/x64/macro-assembler-x64.cc:5009: subp(value, Immediate(kHeapObjectTag));
On 2016/04/19 at 07:25:39, Benedikt Meurer wrote:
> How about this one instead?
> 
> // TODO(hpayer): Change top and limit to tagged.
> leap(kScratchRegister, Operand(value, -kHeapObjectTag));
> Store(allocation_top, kScratchRegister);

Store already uses the scratch register.

[Benedikt Meurer, 2016-04-19 11:05:18]

LGTM on x64.

[Hannes Payer (out of office), 2016-05-10 07:25:31]

PTAL

[Benedikt Meurer, 2016-05-10 07:27:00]

LGTM.

[Michael Lippautz, 2016-05-10 08:32:58]

General and ia32. Will look at platform-specific ports asap.

https://codereview.chromium.org/1899813003/diff/320001/src/crankshaft/hydroge...
File src/crankshaft/hydrogen-instructions.h (right):

https://codereview.chromium.org/1899813003/diff/320001/src/crankshaft/hydroge...
src/crankshaft/hydrogen-instructions.h:5015: void MakeFoldedAllocation() {
nit: It would probably make more sense to pass the dominator in here and get rid
of UpdateAllocationFoldingDominator.

https://codereview.chromium.org/1899813003/diff/320001/src/crankshaft/hydroge...
src/crankshaft/hydrogen-instructions.h:5175: HValue* dominator =
allocate->allocation_folding_dominator();
nit: If you make this a nullptr check and not use an operand on HAllocate but a
regular field, you could remove all changes initializing a new HAllocate(?)

https://codereview.chromium.org/1899813003/diff/320001/src/crankshaft/ia32/li...
File src/crankshaft/ia32/lithium-codegen-ia32.cc (right):

https://codereview.chromium.org/1899813003/diff/320001/src/crankshaft/ia32/li...
src/crankshaft/ia32/lithium-codegen-ia32.cc:4986: __
mov(Operand::StaticVariable(allocation_top), eax);
***~~~ landmine detected ~~~***

https://codereview.chromium.org/1899813003/diff/320001/src/crankshaft/ia32/li...
File src/crankshaft/ia32/lithium-ia32.cc (right):

https://codereview.chromium.org/1899813003/diff/320001/src/crankshaft/ia32/li...
src/crankshaft/ia32/lithium-ia32.cc:2414: return DefineAsRegister(result);
Why don't we need to add the pointer to the pointer map? What if a deopt happens
right after allocating folded objects?

https://codereview.chromium.org/1899813003/diff/320001/src/heap/spaces.cc
File src/heap/spaces.cc (right):

https://codereview.chromium.org/1899813003/diff/320001/src/heap/spaces.cc#new...
src/heap/spaces.cc:2486: } else if (bytes_left >= 0) {
Still would rather see the else followed by a DCHECK here.

https://codereview.chromium.org/1899813003/diff/320001/src/ia32/macro-assembl...
File src/ia32/macro-assembler-ia32.cc (right):

https://codereview.chromium.org/1899813003/diff/320001/src/ia32/macro-assembl...
src/ia32/macro-assembler-ia32.cc:1708: if (((flags & ALLOCATION_FOLDED) == 0) &&
((flags & PRETENURE) != 0)) {
This does not make sense. We should never be in Allocate with ALLOCATION_FOLDED
== 1.

https://codereview.chromium.org/1899813003/diff/320001/src/profiler/sampling-...
File src/profiler/sampling-heap-profiler.cc (left):

https://codereview.chromium.org/1899813003/diff/320001/src/profiler/sampling-...
src/profiler/sampling-heap-profiler.cc:113: sample->global.SetWeak(sample,
OnWeakCallback, WeakCallbackType::kParameter);
Left over? Rebase needed?

[Michael Lippautz, 2016-05-10 09:04:11]

lgtm w comments

https://codereview.chromium.org/1899813003/diff/320001/src/crankshaft/arm64/l...
File src/crankshaft/arm64/lithium-codegen-arm64.cc (right):

https://codereview.chromium.org/1899813003/diff/320001/src/crankshaft/arm64/l...
src/crankshaft/arm64/lithium-codegen-arm64.cc:1510: Register top_address = x10;
Please ack that this is a valid scratch register on arm64.

https://codereview.chromium.org/1899813003/diff/320001/src/mips/macro-assembl...
File src/mips/macro-assembler-mips.cc (right):

https://codereview.chromium.org/1899813003/diff/320001/src/mips/macro-assembl...
src/mips/macro-assembler-mips.cc:4141: if (((flags & ALLOCATION_FOLDED) == 0) &&
((flags & DOUBLE_ALIGNMENT) != 0)) {
Same as w/ other platforms: Remove ALLOCATION_FOLDED check.

https://codereview.chromium.org/1899813003/diff/320001/src/mips64/macro-assem...
File src/mips64/macro-assembler-mips64.cc (right):

https://codereview.chromium.org/1899813003/diff/320001/src/mips64/macro-assem...
src/mips64/macro-assembler-mips64.cc:4449: // the same alignment on ARM64.
s/ARM64/MIPS64/

https://codereview.chromium.org/1899813003/diff/320001/src/mips64/macro-assem...
src/mips64/macro-assembler-mips64.cc:4480: // the same alignment on ARM64.
s/ARM64/MIPS64/

https://codereview.chromium.org/1899813003/diff/320001/src/x87/macro-assemble...
File src/x87/macro-assembler-x87.cc (right):

https://codereview.chromium.org/1899813003/diff/320001/src/x87/macro-assemble...
src/x87/macro-assembler-x87.cc:1650: if (((flags & ALLOCATION_FOLDED) == 0) &&
((flags & PRETENURE) != 0)) {
Same as w/ other platforms: Remove ALLOCATION_FOLDED check.

[Hannes Payer (out of office), 2016-05-10 09:04:45]

https://codereview.chromium.org/1899813003/diff/320001/src/crankshaft/hydroge...
File src/crankshaft/hydrogen-instructions.h (right):

https://codereview.chromium.org/1899813003/diff/320001/src/crankshaft/hydroge...
src/crankshaft/hydrogen-instructions.h:5015: void MakeFoldedAllocation() {
On 2016/05/10 at 08:32:57, Michael Lippautz wrote:
> nit: It would probably make more sense to pass the dominator in here and get
rid of UpdateAllocationFoldingDominator.

Done.

https://codereview.chromium.org/1899813003/diff/320001/src/crankshaft/hydroge...
src/crankshaft/hydrogen-instructions.h:5175: HValue* dominator =
allocate->allocation_folding_dominator();
On 2016/05/10 at 08:32:57, Michael Lippautz wrote:
> nit: If you make this a nullptr check and not use an operand on HAllocate but
a regular field, you could remove all changes initializing a new HAllocate(?)

This is not possible. The input has to be a valid operation.

https://codereview.chromium.org/1899813003/diff/320001/src/crankshaft/ia32/li...
File src/crankshaft/ia32/lithium-ia32.cc (right):

https://codereview.chromium.org/1899813003/diff/320001/src/crankshaft/ia32/li...
src/crankshaft/ia32/lithium-ia32.cc:2414: return DefineAsRegister(result);
On 2016/05/10 at 08:32:58, Michael Lippautz wrote:
> Why don't we need to add the pointer to the pointer map? What if a deopt
happens right after allocating folded objects?

A folded allocation does not need a safepoint.

https://codereview.chromium.org/1899813003/diff/320001/src/heap/spaces.cc
File src/heap/spaces.cc (right):

https://codereview.chromium.org/1899813003/diff/320001/src/heap/spaces.cc#new...
src/heap/spaces.cc:2486: } else if (bytes_left >= 0) {
On 2016/05/10 at 08:32:58, Michael Lippautz wrote:
> Still would rather see the else followed by a DCHECK here.

Done.

https://codereview.chromium.org/1899813003/diff/320001/src/ia32/macro-assembl...
File src/ia32/macro-assembler-ia32.cc (right):

https://codereview.chromium.org/1899813003/diff/320001/src/ia32/macro-assembl...
src/ia32/macro-assembler-ia32.cc:1708: if (((flags & ALLOCATION_FOLDED) == 0) &&
((flags & PRETENURE) != 0)) {
On 2016/05/10 at 08:32:58, Michael Lippautz wrote:
> This does not make sense. We should never be in Allocate with
ALLOCATION_FOLDED == 1.

leftover, removed.

https://codereview.chromium.org/1899813003/diff/320001/src/profiler/sampling-...
File src/profiler/sampling-heap-profiler.cc (left):

https://codereview.chromium.org/1899813003/diff/320001/src/profiler/sampling-...
src/profiler/sampling-heap-profiler.cc:113: sample->global.SetWeak(sample,
OnWeakCallback, WeakCallbackType::kParameter);
On 2016/05/10 at 08:32:58, Michael Lippautz wrote:
> Left over? Rebase needed?

Strange. Done.

[Hannes Payer (out of office), 2016-05-10 09:10:59]

https://codereview.chromium.org/1899813003/diff/320001/src/crankshaft/arm64/l...
File src/crankshaft/arm64/lithium-codegen-arm64.cc (right):

https://codereview.chromium.org/1899813003/diff/320001/src/crankshaft/arm64/l...
src/crankshaft/arm64/lithium-codegen-arm64.cc:1510: Register top_address = x10;
On 2016/05/10 at 09:04:10, Michael Lippautz wrote:
> Please ack that this is a valid scratch register on arm64.
ack.

https://codereview.chromium.org/1899813003/diff/320001/src/mips/macro-assembl...
File src/mips/macro-assembler-mips.cc (right):

https://codereview.chromium.org/1899813003/diff/320001/src/mips/macro-assembl...
src/mips/macro-assembler-mips.cc:4141: if (((flags & ALLOCATION_FOLDED) == 0) &&
((flags & DOUBLE_ALIGNMENT) != 0)) {
On 2016/05/10 at 09:04:10, Michael Lippautz wrote:
> Same as w/ other platforms: Remove ALLOCATION_FOLDED check.

Done.

https://codereview.chromium.org/1899813003/diff/320001/src/mips64/macro-assem...
File src/mips64/macro-assembler-mips64.cc (right):

https://codereview.chromium.org/1899813003/diff/320001/src/mips64/macro-assem...
src/mips64/macro-assembler-mips64.cc:4449: // the same alignment on ARM64.
On 2016/05/10 at 09:04:10, Michael Lippautz wrote:
> s/ARM64/MIPS64/

Done.

https://codereview.chromium.org/1899813003/diff/320001/src/mips64/macro-assem...
src/mips64/macro-assembler-mips64.cc:4480: // the same alignment on ARM64.
On 2016/05/10 at 09:04:10, Michael Lippautz wrote:
> s/ARM64/MIPS64/

Done.

https://codereview.chromium.org/1899813003/diff/320001/src/x87/macro-assemble...
File src/x87/macro-assembler-x87.cc (right):

https://codereview.chromium.org/1899813003/diff/320001/src/x87/macro-assemble...
src/x87/macro-assembler-x87.cc:1650: if (((flags & ALLOCATION_FOLDED) == 0) &&
((flags & PRETENURE) != 0)) {
On 2016/05/10 at 09:04:10, Michael Lippautz wrote:
> Same as w/ other platforms: Remove ALLOCATION_FOLDED check.

Done.

[Hannes Payer (out of office), 2016-05-10 09:29:38]

The CQ bit was checked by hpayer@chromium.org

[Hannes Payer (out of office), 2016-05-10 09:29:39]

The patchset sent to the CQ was uploaded after l-g-t-m from
bmeurer@chromium.org, mlippautz@chromium.org
Link to the patchset: https://codereview.chromium.org/1899813003/#ps360001
(title: " ")

[commit-bot: I haz the power, 2016-05-10 09:29:42]

CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/1899813003/360001
View timeline at
 https://chromium-cq-status.appspot.com/patch-timeline/1899813003/360001

[commit-bot: I haz the power, 2016-05-10 09:49:54]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2016-05-10 09:49:55]

Try jobs failed on following builders:
  v8_mac_rel_ng on tryserver.v8 (JOB_FAILED,
http://build.chromium.org/p/tryserver.v8/builders/v8_mac_rel_ng/builds/1389)
  v8_mac_rel_ng_triggered on tryserver.v8 (JOB_FAILED,
http://build.chromium.org/p/tryserver.v8/builders/v8_mac_rel_ng_triggered/bui...)

[Hannes Payer (out of office), 2016-05-10 10:44:36]

The CQ bit was checked by hpayer@chromium.org

[Hannes Payer (out of office), 2016-05-10 10:44:37]

The patchset sent to the CQ was uploaded after l-g-t-m from
bmeurer@chromium.org, mlippautz@chromium.org
Link to the patchset: https://codereview.chromium.org/1899813003/#ps380001
(title: " ")

[commit-bot: I haz the power, 2016-05-10 10:44:43]

CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/1899813003/380001
View timeline at
 https://chromium-cq-status.appspot.com/patch-timeline/1899813003/380001

[commit-bot: I haz the power, 2016-05-10 10:46:12]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2016-05-10 10:46:13]

Try jobs failed on following builders:
  v8_android_arm_compile_rel on tryserver.v8 (JOB_FAILED,
http://build.chromium.org/p/tryserver.v8/builders/v8_android_arm_compile_rel/...)
  v8_linux64_asan_rel_ng on tryserver.v8 (JOB_FAILED,
http://build.chromium.org/p/tryserver.v8/builders/v8_linux64_asan_rel_ng/buil...)
  v8_linux64_avx2_rel_ng on tryserver.v8 (JOB_FAILED,
http://build.chromium.org/p/tryserver.v8/builders/v8_linux64_avx2_rel_ng/buil...)
  v8_linux64_rel_ng on tryserver.v8 (JOB_FAILED,
http://build.chromium.org/p/tryserver.v8/builders/v8_linux64_rel_ng/builds/5515)
  v8_linux_arm64_rel_ng on tryserver.v8 (JOB_FAILED,
http://build.chromium.org/p/tryserver.v8/builders/v8_linux_arm64_rel_ng/build...)
  v8_linux_arm_rel_ng on tryserver.v8 (JOB_FAILED,
http://build.chromium.org/p/tryserver.v8/builders/v8_linux_arm_rel_ng/builds/...)
  v8_linux_gcc_compile_rel on tryserver.v8 (JOB_FAILED,
http://build.chromium.org/p/tryserver.v8/builders/v8_linux_gcc_compile_rel/bu...)
  v8_linux_mips64el_compile_rel on tryserver.v8 (JOB_FAILED,
http://build.chromium.org/p/tryserver.v8/builders/v8_linux_mips64el_compile_r...)
  v8_linux_mipsel_compile_rel on tryserver.v8 (JOB_FAILED,
http://build.chromium.org/p/tryserver.v8/builders/v8_linux_mipsel_compile_rel...)
  v8_linux_nodcheck_rel_ng on tryserver.v8 (JOB_FAILED,
http://build.chromium.org/p/tryserver.v8/builders/v8_linux_nodcheck_rel_ng/bu...)
  v8_linux_rel_ng on tryserver.v8 (JOB_FAILED,
http://build.chromium.org/p/tryserver.v8/builders/v8_linux_rel_ng/builds/5503)
  v8_presubmit on tryserver.v8 (JOB_FAILED,
http://build.chromium.org/p/tryserver.v8/builders/v8_presubmit/builds/14941)

[Hannes Payer (out of office), 2016-05-10 10:55:27]

The CQ bit was checked by hpayer@chromium.org

[Hannes Payer (out of office), 2016-05-10 10:55:30]

The patchset sent to the CQ was uploaded after l-g-t-m from
bmeurer@chromium.org, mlippautz@chromium.org
Link to the patchset: https://codereview.chromium.org/1899813003/#ps400001
(title: " ")

[commit-bot: I haz the power, 2016-05-10 10:55:39]

CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/1899813003/400001
View timeline at
 https://chromium-cq-status.appspot.com/patch-timeline/1899813003/400001

[commit-bot: I haz the power, 2016-05-10 11:29:02]

Committed patchset #21 (id:400001)

[commit-bot: I haz the power, 2016-05-10 11:29:18]

Description was changed from

==========
[crankshaft] Fragmentation-free allocation folding.

The new allocation folding implementation avoids fragmentation between folded
allocation. As a consequence, our heap will always be iterable i.e. we do not
have to perform a garbage collection before iterating the heap.

BUG=chromium:580959
LOG=n
==========

to

==========
[crankshaft] Fragmentation-free allocation folding.

The new allocation folding implementation avoids fragmentation between folded
allocation. As a consequence, our heap will always be iterable i.e. we do not
have to perform a garbage collection before iterating the heap.

BUG=chromium:580959
LOG=n

Committed: https://crrev.com/61f5fbbb1926e1ffb672214a043e8c98db0e8af6
Cr-Commit-Position: refs/heads/master@{#36133}
==========

[commit-bot: I haz the power, 2016-05-10 11:29:19]

Patchset 21 (id:??) landed as
https://crrev.com/61f5fbbb1926e1ffb672214a043e8c98db0e8af6
Cr-Commit-Position: refs/heads/master@{#36133}