Improve and simplify removal of unreachable code

Improve and simplify removal of unreachable code

- Detect unreachable basic blocks of code either following an unconditional deopt or after a provably untaken branch of HBranch or HCompareObjectEqAndBranch instructions.
- Emit dummy uses in unreachable blocks during Hydrogen -> Lithium translation.

BUG=chromium:258519
R=jkummerow@chromium.org, mstarzinger@chromium.org

Committed: http://code.google.com/p/v8/source/detail?r=17073

[danno, 2013-08-14 14:51:44]

PTAL

[Michael Starzinger, 2013-08-16 15:02:20]

LGTM with a couple of comments.

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

https://codereview.chromium.org/22876009/diff/13001/src/hydrogen-instructions...
src/hydrogen-instructions.h:3393: bool SameConstantObject(HConstant* other) {
nit: Let's rename this to just "SameConstant", it doesn't look specific to
objects.

https://codereview.chromium.org/22876009/diff/13001/src/hydrogen-instructions...
src/hydrogen-instructions.h:3394: if (HasSmiValue() && other->HasSmiValue()) {
Shouldn't this be HasInteger32Value in these checks? Also what about
HasDoubleValue?

https://codereview.chromium.org/22876009/diff/13001/src/hydrogen.cc
File src/hydrogen.cc (right):

https://codereview.chromium.org/22876009/diff/13001/src/hydrogen.cc#newcode8028
src/hydrogen.cc:8028: return !right->IsConstant() ||
nit: Should fit into one line.

https://codereview.chromium.org/22876009/diff/13001/src/hydrogen.cc#newcode8032
src/hydrogen.cc:8032: return !left->IsConstant() ||
nit: Should fit into one line.

https://codereview.chromium.org/22876009/diff/13001/src/lithium.cc
File src/lithium.cc (right):

https://codereview.chromium.org/22876009/diff/13001/src/lithium.cc#newcode509
src/lithium.cc:509: void LChunkBuilder::PropagateUnreachableBlockMarks() {
As discussed offline: This looks like it should be done as a separate hydrogen
phase (similar to HPropagateDeoptimizingMarkPhase) instead of as part of the
lithium chunk builder. But I am totally fine with leaving this for a follow-up
CL to cleanup, in which case I would put a TODO here.

[Jakob Kummerow, 2013-08-20 08:46:55]

LGTM with comments.

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

https://codereview.chromium.org/22876009/diff/13001/src/hydrogen-instructions...
src/hydrogen-instructions.h:3393: bool SameConstantObject(HConstant* other) {
This seems to cover a subset of the functionality of DataEquals() below. Maybe
re-use that instead? If you actually need the specialized behavior then that's
fine of course.

https://codereview.chromium.org/22876009/diff/13001/src/lithium.cc
File src/lithium.cc (right):

https://codereview.chromium.org/22876009/diff/13001/src/lithium.cc#newcode512
src/lithium.cc:512: if (graph()->HasUnreachableCode()) {
You can avoid a level of indentation by turning this into an early return:
if (!graph()->HasUnreachableCode()) return;

[Jakob Kummerow, 2013-08-30 11:52:43]

Since the issue that's fixed by this CL has reached the stable channel
(crbug.com/280333), I've pulled out the actual fix and the regression test in
https://codereview.chromium.org/23623009/.

We should still land the additional work to avoid generating unreachable code,
but that's less urgent (and possibly not safe enough for a backmerge to stable).

https://codereview.chromium.org/22876009/diff/13001/src/lithium.cc
File src/lithium.cc (right):

https://codereview.chromium.org/22876009/diff/13001/src/lithium.cc#newcode509
src/lithium.cc:509: void LChunkBuilder::PropagateUnreachableBlockMarks() {
Am I missing something, or is this method never called?

[danno, 2013-10-01 10:43:17]

Please take another look. This is a bigger re-write that moves all the logic
into Hydrogen and unifies a bunch of unreachable code handling with deopt block
handling.

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

https://codereview.chromium.org/22876009/diff/13001/src/hydrogen-instructions...
src/hydrogen-instructions.h:3393: bool SameConstantObject(HConstant* other) {
On 2013/08/16 15:02:20, Michael Starzinger wrote:
> nit: Let's rename this to just "SameConstant", it doesn't look specific to
> objects.

Actually, I use DataEquals now. Makes it even simpler.

https://codereview.chromium.org/22876009/diff/13001/src/hydrogen-instructions...
src/hydrogen-instructions.h:3394: if (HasSmiValue() && other->HasSmiValue()) {
On 2013/08/16 15:02:20, Michael Starzinger wrote:
> Shouldn't this be HasInteger32Value in these checks? Also what about
> HasDoubleValue?

See above.

https://codereview.chromium.org/22876009/diff/13001/src/hydrogen.cc
File src/hydrogen.cc (right):

https://codereview.chromium.org/22876009/diff/13001/src/hydrogen.cc#newcode8028
src/hydrogen.cc:8028: return !right->IsConstant() ||
On 2013/08/16 15:02:20, Michael Starzinger wrote:
> nit: Should fit into one line.

Done.

https://codereview.chromium.org/22876009/diff/13001/src/hydrogen.cc#newcode8032
src/hydrogen.cc:8032: return !left->IsConstant() ||
On 2013/08/16 15:02:20, Michael Starzinger wrote:
> nit: Should fit into one line.

Done.

[Michael Starzinger, 2013-10-01 11:17:46]

LMBTMN (looks much better to me now; that implies LGTM). Another round of nits.

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

https://codereview.chromium.org/22876009/diff/71027/src/flag-definitions.h#ne...
src/flag-definitions.h:297: DEFINE_bool(unreachable_code_elimination, true,
nit: Looks like it fits into one line now.

https://codereview.chromium.org/22876009/diff/71027/src/hydrogen-instructions.cc
File src/hydrogen-instructions.cc (right):

https://codereview.chromium.org/22876009/diff/71027/src/hydrogen-instructions...
src/hydrogen-instructions.cc:2889:
HConstant::cast(left())->DataEquals(HConstant::cast(right()));
suggestion: We could use Equals() instead of DataEquals() here. Admittedly that
performs some redundant checks, but would allow us to keep
HConstant::DataEquals() protected and not break abstraction. I am fine either
way, your choice.

https://codereview.chromium.org/22876009/diff/71027/src/hydrogen-mark-unreach...
File src/hydrogen-mark-unreachable.h (right):

https://codereview.chromium.org/22876009/diff/71027/src/hydrogen-mark-unreach...
src/hydrogen-mark-unreachable.h:40: : HPhase("H_Propagate unrechable mark",
graph) { }
nit: s/H_Propagate unrechable mark/H_Mark unreachable/

https://codereview.chromium.org/22876009/diff/71027/src/ia32/lithium-codegen-...
File src/ia32/lithium-codegen-ia32.h (right):

https://codereview.chromium.org/22876009/diff/71027/src/ia32/lithium-codegen-...
src/ia32/lithium-codegen-ia32.h:35: #include "lithium-codegen.h"
nit: Can we alpha-sort the includes.

https://codereview.chromium.org/22876009/diff/71027/src/lithium-codegen.cc
File src/lithium-codegen.cc (right):

https://codereview.chromium.org/22876009/diff/71027/src/lithium-codegen.cc#ne...
src/lithium-codegen.cc:144: #undef __
nit: Looks obsolete, let's drop it.

https://codereview.chromium.org/22876009/diff/71027/src/lithium-codegen.h
File src/lithium-codegen.h (right):

https://codereview.chromium.org/22876009/diff/71027/src/lithium-codegen.h#new...
src/lithium-codegen.h:41: class LCodeGenBase V8_FINAL BASE_EMBEDDED {
This V8_FINAL looks wrong because we actually inherit from this class. Doesn't
actually speak for the usefulness off these macros in the first place. :)

https://codereview.chromium.org/22876009/diff/71027/src/lithium-codegen.h#new...
src/lithium-codegen.h:94: #undef __
nit: Looks obsolete, let's drop it.

[Jakob Kummerow, 2013-10-01 11:59:19]

LGTM with comments.

https://codereview.chromium.org/22876009/diff/71027/src/arm/lithium-arm.cc
File src/arm/lithium-arm.cc (right):

https://codereview.chromium.org/22876009/diff/71027/src/arm/lithium-arm.cc#ne...
src/arm/lithium-arm.cc:872: new(zone())
LDummyUse(UseAny(current->OperandAt(1)));
OperandAt(i)

https://codereview.chromium.org/22876009/diff/71027/src/hydrogen-mark-unreach...
File src/hydrogen-mark-unreachable.cc (right):

https://codereview.chromium.org/22876009/diff/71027/src/hydrogen-mark-unreach...
src/hydrogen-mark-unreachable.cc:43: if (block->IsReachable()) {
nit: you can avoid one level of indentation by turning this into an early
return:
      if (block->IsUnreachable()) continue;

https://codereview.chromium.org/22876009/diff/71027/src/hydrogen.cc
File src/hydrogen.cc (right):

https://codereview.chromium.org/22876009/diff/71027/src/hydrogen.cc#newcode3635
src/hydrogen.cc:3635: // If the current test block is deoptimizing due to an
unhandle clause
nit: unhandled

https://codereview.chromium.org/22876009/diff/71027/src/hydrogen.cc#newcode3636
src/hydrogen.cc:3636: // of the switch, the test instruction is in the next
block since (the
nit: no ()

https://codereview.chromium.org/22876009/diff/71027/src/ia32/lithium-ia32.cc
File src/ia32/lithium-ia32.cc (right):

https://codereview.chromium.org/22876009/diff/71027/src/ia32/lithium-ia32.cc#...
src/ia32/lithium-ia32.cc:916: ? graph()->GetConstant1() :
nit: please put the ':' in the next line, under the '?'. Or move the next line
up here, right behind the ':'.

https://codereview.chromium.org/22876009/diff/71027/src/ia32/lithium-ia32.cc#...
src/ia32/lithium-ia32.cc:921: new(zone())
LDummyUse(UseAny(current->OperandAt(1)));
bug: OperandAt(i)!

https://codereview.chromium.org/22876009/diff/71027/src/x64/lithium-x64.cc
File src/x64/lithium-x64.cc (right):

https://codereview.chromium.org/22876009/diff/71027/src/x64/lithium-x64.cc#ne...
src/x64/lithium-x64.cc:872: new(zone())
LDummyUse(UseAny(current->OperandAt(1)));
OperandAt(i)!

https://codereview.chromium.org/22876009/diff/71027/test/mjsunit/constant-bra...
File test/mjsunit/constant-branch-folding-liveness.js (right):

https://codereview.chromium.org/22876009/diff/71027/test/mjsunit/constant-bra...
test/mjsunit/constant-branch-folding-liveness.js:1: // Copyright 2013 the V8
project authors. All rights reserved.
You can drop this file; it is already present as
test/mjsunit/regress/regress-crbug-280333.js.

[Jakob Kummerow, 2013-10-01 17:47:12]

one more nit.

https://codereview.chromium.org/22876009/diff/71027/src/hydrogen-mark-unreach...
File src/hydrogen-mark-unreachable.cc (right):

https://codereview.chromium.org/22876009/diff/71027/src/hydrogen-mark-unreach...
src/hydrogen-mark-unreachable.cc:47: // A block is reachable if one of it's
predecessor is reachable,
nit: s/it's predecessor/its predecessors/

[danno, 2013-10-02 11:45:48]

Committed patchset #22 manually as r17073 (presubmit successful).

[danno, 2013-10-23 11:46:51]

Addressed and landed

https://codereview.chromium.org/22876009/diff/71027/src/arm/lithium-arm.cc
File src/arm/lithium-arm.cc (right):

https://codereview.chromium.org/22876009/diff/71027/src/arm/lithium-arm.cc#ne...
src/arm/lithium-arm.cc:872: new(zone())
LDummyUse(UseAny(current->OperandAt(1)));
On 2013/10/01 11:59:20, Jakob wrote:
> OperandAt(i)

Done.

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

https://codereview.chromium.org/22876009/diff/71027/src/flag-definitions.h#ne...
src/flag-definitions.h:297: DEFINE_bool(unreachable_code_elimination, true,
On 2013/10/01 11:17:47, Michael Starzinger wrote:
> nit: Looks like it fits into one line now.

Done.

https://codereview.chromium.org/22876009/diff/71027/src/hydrogen-instructions.cc
File src/hydrogen-instructions.cc (right):

https://codereview.chromium.org/22876009/diff/71027/src/hydrogen-instructions...
src/hydrogen-instructions.cc:2889:
HConstant::cast(left())->DataEquals(HConstant::cast(right()));
On 2013/10/01 11:17:47, Michael Starzinger wrote:
> suggestion: We could use Equals() instead of DataEquals() here. Admittedly
that
> performs some redundant checks, but would allow us to keep
> HConstant::DataEquals() protected and not break abstraction. I am fine either
> way, your choice.

Done.

https://codereview.chromium.org/22876009/diff/71027/src/hydrogen-mark-unreach...
File src/hydrogen-mark-unreachable.cc (right):

https://codereview.chromium.org/22876009/diff/71027/src/hydrogen-mark-unreach...
src/hydrogen-mark-unreachable.cc:43: if (block->IsReachable()) {
On 2013/10/01 11:59:20, Jakob wrote:
> nit: you can avoid one level of indentation by turning this into an early
> return:
>       if (block->IsUnreachable()) continue;

Done.

https://codereview.chromium.org/22876009/diff/71027/src/hydrogen-mark-unreach...
src/hydrogen-mark-unreachable.cc:47: // A block is reachable if one of it's
predecessor is reachable,
On 2013/10/01 17:47:13, Jakob wrote:
> nit: s/it's predecessor/its predecessors/

Done.

https://codereview.chromium.org/22876009/diff/71027/src/hydrogen-mark-unreach...
File src/hydrogen-mark-unreachable.h (right):

https://codereview.chromium.org/22876009/diff/71027/src/hydrogen-mark-unreach...
src/hydrogen-mark-unreachable.h:40: : HPhase("H_Propagate unrechable mark",
graph) { }
On 2013/10/01 11:17:47, Michael Starzinger wrote:
> nit: s/H_Propagate unrechable mark/H_Mark unreachable/

Done.

https://codereview.chromium.org/22876009/diff/71027/src/hydrogen.cc
File src/hydrogen.cc (right):

https://codereview.chromium.org/22876009/diff/71027/src/hydrogen.cc#newcode3635
src/hydrogen.cc:3635: // If the current test block is deoptimizing due to an
unhandle clause
On 2013/10/01 11:59:20, Jakob wrote:
> nit: unhandled

Done.

https://codereview.chromium.org/22876009/diff/71027/src/hydrogen.cc#newcode3636
src/hydrogen.cc:3636: // of the switch, the test instruction is in the next
block since (the
On 2013/10/01 11:59:20, Jakob wrote:
> nit: no ()

Done.

https://codereview.chromium.org/22876009/diff/71027/src/ia32/lithium-codegen-...
File src/ia32/lithium-codegen-ia32.h (right):

https://codereview.chromium.org/22876009/diff/71027/src/ia32/lithium-codegen-...
src/ia32/lithium-codegen-ia32.h:35: #include "lithium-codegen.h"
On 2013/10/01 11:17:47, Michael Starzinger wrote:
> nit: Can we alpha-sort the includes.

Done.

https://codereview.chromium.org/22876009/diff/71027/src/ia32/lithium-ia32.cc
File src/ia32/lithium-ia32.cc (right):

https://codereview.chromium.org/22876009/diff/71027/src/ia32/lithium-ia32.cc#...
src/ia32/lithium-ia32.cc:916: ? graph()->GetConstant1() :
On 2013/10/01 11:59:20, Jakob wrote:
> nit: please put the ':' in the next line, under the '?'. Or move the next line
> up here, right behind the ':'.

Done.

https://codereview.chromium.org/22876009/diff/71027/src/ia32/lithium-ia32.cc#...
src/ia32/lithium-ia32.cc:921: new(zone())
LDummyUse(UseAny(current->OperandAt(1)));
On 2013/10/01 11:59:20, Jakob wrote:
> bug: OperandAt(i)!

Done.

https://codereview.chromium.org/22876009/diff/71027/src/lithium-codegen.cc
File src/lithium-codegen.cc (right):

https://codereview.chromium.org/22876009/diff/71027/src/lithium-codegen.cc#ne...
src/lithium-codegen.cc:144: #undef __
On 2013/10/01 11:17:47, Michael Starzinger wrote:
> nit: Looks obsolete, let's drop it.

Done.

https://codereview.chromium.org/22876009/diff/71027/src/lithium-codegen.h
File src/lithium-codegen.h (right):

https://codereview.chromium.org/22876009/diff/71027/src/lithium-codegen.h#new...
src/lithium-codegen.h:41: class LCodeGenBase V8_FINAL BASE_EMBEDDED {
On 2013/10/01 11:17:47, Michael Starzinger wrote:
> This V8_FINAL looks wrong because we actually inherit from this class. Doesn't
> actually speak for the usefulness off these macros in the first place. :)

Done.

https://codereview.chromium.org/22876009/diff/71027/src/lithium-codegen.h#new...
src/lithium-codegen.h:94: #undef __
On 2013/10/01 11:17:47, Michael Starzinger wrote:
> nit: Looks obsolete, let's drop it.

Done.

https://codereview.chromium.org/22876009/diff/71027/src/x64/lithium-x64.cc
File src/x64/lithium-x64.cc (right):

https://codereview.chromium.org/22876009/diff/71027/src/x64/lithium-x64.cc#ne...
src/x64/lithium-x64.cc:872: new(zone())
LDummyUse(UseAny(current->OperandAt(1)));
On 2013/10/01 11:59:20, Jakob wrote:
> OperandAt(i)!

Done.

https://codereview.chromium.org/22876009/diff/71027/test/mjsunit/constant-bra...
File test/mjsunit/constant-branch-folding-liveness.js (right):

https://codereview.chromium.org/22876009/diff/71027/test/mjsunit/constant-bra...
test/mjsunit/constant-branch-folding-liveness.js:1: // Copyright 2013 the V8
project authors. All rights reserved.
On 2013/10/01 11:59:20, Jakob wrote:
> You can drop this file; it is already present as
> test/mjsunit/regress/regress-crbug-280333.js.

Done.