R=bmeurer@chromium.org
TEST=presubmit

Review URL: https://codereview.chromium.org/905293002

Cr-Commit-Position: refs/heads/master@{#26525}

If a (pure) node has two or more uses, but there exists a path from the
common dominator of these uses to end, which does not contain a use,
then we split the node such that no unnecessary computation takes place.
Note however, that this only applies if the node cannot be hoisted out
of a loop.

BUG=v8:3864
LOG=n
R=jarin@chromium.org

Review URL: https://codereview.chromium.org/899433005

Cr-Commit-Position: refs/heads/master@{#26404}

Also add some unittests for the dominator stuff.

R=mstarzinger@chromium.org

Review URL: https://codereview.chromium.org/865393004

Cr-Commit-Position: refs/heads/master@{#26241}

- Move unit tests to schedule-unittests.cc.
- Remove pre-C++11 cruft.
- Fix some include weirdness.

R=mstarzinger@chromium.org

Review URL: https://codereview.chromium.org/864293002

Cr-Commit-Position: refs/heads/master@{#26220}

R=titzer@chromium.org

Review URL: https://codereview.chromium.org/753063004

Cr-Commit-Position: refs/heads/master@{#25622}

R=jarin@chromium.org
TEST=cctest/test-scheduler/NestedFloatingDiamondWithChain

Review URL: https://codereview.chromium.org/738613005

Cr-Commit-Position: refs/heads/master@{#25621}

R=titzer@chromium.org

Review URL: https://codereview.chromium.org/761673004

Cr-Commit-Position: refs/heads/master@{#25543}

R=bmeurer@chromium.org

Review URL: https://codereview.chromium.org/755353003

Cr-Commit-Position: refs/heads/master@{#25525}

R=dcarney@chromium.org

Review URL: https://codereview.chromium.org/711413002

Cr-Commit-Position: refs/heads/master@{#25265}
git-svn-id: https://v8.googlecode.com/svn/branches/bleeding_edge@25265 ce2b1a6d-e550-0410-aec6-3dcde31c8c00

This contains the following changes squashed together:
- Switch BasicBlock::loop_end to be a basic block instead of an RPO.
- Switch ScheduleLate to use dominator depth instead of RPO.
- Switch ScheduleEarly to use dominator depth instead of RPO.
- Push out absolute RPO ordering everywhere else in the scheduler.
- Keep linked list of blocks in RPO order while scheduling.
- Switch from RPO number to depth for dominator calculation.

R=jarin@chromium.org

Review URL: https://codereview.chromium.org/696363002

Cr-Commit-Position: refs/heads/master@{#25138}
git-svn-id: https://v8.googlecode.com/svn/branches/bleeding_edge@25138 ce2b1a6d-e550-0410-aec6-3dcde31c8c00

R=titzer@chromium.org, jarin@chromium.org

Review URL: https://codereview.chromium.org/687133003

Cr-Commit-Position: refs/heads/master@{#24991}
git-svn-id: https://v8.googlecode.com/svn/branches/bleeding_edge@24991 ce2b1a6d-e550-0410-aec6-3dcde31c8c00

R=jarin@chromium.org

Review URL: https://codereview.chromium.org/685773002

Cr-Commit-Position: refs/heads/master@{#24968}
git-svn-id: https://v8.googlecode.com/svn/branches/bleeding_edge@24968 ce2b1a6d-e550-0410-aec6-3dcde31c8c00

R=jarin@chromium.org

Review URL: https://codereview.chromium.org/673753003

git-svn-id: https://v8.googlecode.com/svn/branches/bleeding_edge@24853 ce2b1a6d-e550-0410-aec6-3dcde31c8c00

R=jarin@chromium.org

Review URL: https://codereview.chromium.org/673513004

git-svn-id: https://v8.googlecode.com/svn/branches/bleeding_edge@24833 ce2b1a6d-e550-0410-aec6-3dcde31c8c00

TBR=jarin@chromium.org

Review URL: https://codereview.chromium.org/654583004

git-svn-id: https://v8.googlecode.com/svn/branches/bleeding_edge@24782 ce2b1a6d-e550-0410-aec6-3dcde31c8c00

R=jarin@chromium.org

Review URL: https://codereview.chromium.org/669683002

git-svn-id: https://v8.googlecode.com/svn/branches/bleeding_edge@24781 ce2b1a6d-e550-0410-aec6-3dcde31c8c00

R=bmeurer@chromium.org

BUG=

Review URL: https://codereview.chromium.org/665893006

git-svn-id: https://v8.googlecode.com/svn/branches/bleeding_edge@24771 ce2b1a6d-e550-0410-aec6-3dcde31c8c00

R=jarin@chromium.org

Review URL: https://codereview.chromium.org/649203002

git-svn-id: https://v8.googlecode.com/svn/branches/bleeding_edge@24568 ce2b1a6d-e550-0410-aec6-3dcde31c8c00

This reverts commit 0ab306041a6eba99fe5e2ef78251de137321f559.

"Fix" make scheduler run out of memory.

TBR=mstarzinger@chromium.org

Review URL: https://codereview.chromium.org/656473002

git-svn-id: https://v8.googlecode.com/svn/branches/bleeding_edge@24566 ce2b1a6d-e550-0410-aec6-3dcde31c8c00

The scheduler rewires control based on the last *control*
node that appears in the schedule of a block. This is not
sufficient to account for dependencies.

This patch adds additional dependencies to floating control
nodes. Given a floating control node A, every non-control
dependency of every node B that depends on A is introduces
as an additional dependency of A.

This allows the scheduler to correctly schedule two
diamonds A, B, if their only correct schedule is to
schedule B into the ifTrue successor in A.

TEST=cctest/test-scheduler/NestedFloatingDiamonds
R=mstarzinger@chromium.org, titzer@chromium.org

Review URL: https://codereview.chromium.org/602083003

git-svn-id: https://v8.googlecode.com/svn/branches/bleeding_edge@24561 ce2b1a6d-e550-0410-aec6-3dcde31c8c00

R=jarin@chromium.org

Review URL: https://codereview.chromium.org/642803003

git-svn-id: https://v8.googlecode.com/svn/branches/bleeding_edge@24526 ce2b1a6d-e550-0410-aec6-3dcde31c8c00

To manage BasicBlock's predecessors and successors we now use plain
std::vector.

The change also moves bunch of method definitions from header files
to implementation files.

In zlib, the change brings 3x improvement in the scheduler's memory
consumption. The --turbo-stats flag says we go 169MB -> 55MB in
the scheduler, 383MB -> 268MB overall.

BUG=
R=bmeurer@chromium.org

Review URL: https://codereview.chromium.org/606403003

git-svn-id: https://v8.googlecode.com/svn/branches/bleeding_edge@24308 ce2b1a6d-e550-0410-aec6-3dcde31c8c00

TBR=mstarzinger@chromium.org
BUG=

Review URL: https://codereview.chromium.org/505193002

git-svn-id: https://v8.googlecode.com/svn/branches/bleeding_edge@23413 ce2b1a6d-e550-0410-aec6-3dcde31c8c00

This CL makes several changes to the scheduling algorithm to handle control
flow that is not connected to End. Such control nodes constitute "floating
control islands" that must be linearized by the schedule. This is done
by considering such nodes to be schedulable, and then editing the control
dependencies after a first pass of scheduling. Then a subsequent pass of
scheduling will place all nodes correctly into the fully connected graph.

R=mstarzinger@chromium.org, rossberg@chromium.org
BUG=

Review URL: https://codereview.chromium.org/499363002

git-svn-id: https://v8.googlecode.com/svn/branches/bleeding_edge@23411 ce2b1a6d-e550-0410-aec6-3dcde31c8c00

to use with Zone. For example, subclasses add constructors that wrap a Zone
in a zone_allocator to save clients this verbosity.

R=bmeurer@chromium.org, mstarzinger@chromium.org
BUG=

Review URL: https://codereview.chromium.org/505133003

git-svn-id: https://v8.googlecode.com/svn/branches/bleeding_edge@23402 ce2b1a6d-e550-0410-aec6-3dcde31c8c00

Refactor Scheduler to simplify construction of CFG from sea of nodes. Use PreEdge/Post as part of the graph tarversal, and make finding of successor projections more robust.

R=jarin@chromium.org
BUG=

Review URL: https://codereview.chromium.org/490483002

git-svn-id: https://v8.googlecode.com/svn/branches/bleeding_edge@23217 ce2b1a6d-e550-0410-aec6-3dcde31c8c00

Move some methods from OperatorProperties into Scheduler that are only related to scheduling. Now these methods take a Node* parameter, as decisions relating floating control need distinguish not just operators but nodes.

R=bmeurer@chromium.org
BUG=

Review URL: https://codereview.chromium.org/474983003

git-svn-id: https://v8.googlecode.com/svn/branches/bleeding_edge@23160 ce2b1a6d-e550-0410-aec6-3dcde31c8c00

R=jarin@chromium.org
BUG=

Review URL: https://codereview.chromium.org/478253002

git-svn-id: https://v8.googlecode.com/svn/branches/bleeding_edge@23145 ce2b1a6d-e550-0410-aec6-3dcde31c8c00

R=titzer@chromium.org, bmeurer@chromium.org

Review URL: https://codereview.chromium.org/467103003

git-svn-id: https://v8.googlecode.com/svn/branches/bleeding_edge@23103 ce2b1a6d-e550-0410-aec6-3dcde31c8c00

TBR=bmeurer@chromium.org
BUG=

Review URL: https://codereview.chromium.org/460683003

git-svn-id: https://v8.googlecode.com/svn/branches/bleeding_edge@23040 ce2b1a6d-e550-0410-aec6-3dcde31c8c00

Remove duplication in Scheduler and simplify interface. Make ComputeSchedule() and ComputeSpecialRPO() the only interface used by clients.

R=bmeurer@chromium.org
BUG=

Review URL: https://codereview.chromium.org/460633002

git-svn-id: https://v8.googlecode.com/svn/branches/bleeding_edge@23039 ce2b1a6d-e550-0410-aec6-3dcde31c8c00

This way we don't clash with the ASSERT* macros
defined by GoogleTest, and we are one step closer
to being able to replace our homegrown base/ with
base/ from Chrome.

R=jochen@chromium.org, svenpanne@chromium.org

Review URL: https://codereview.chromium.org/430503007

git-svn-id: https://v8.googlecode.com/svn/branches/bleeding_edge@22812 ce2b1a6d-e550-0410-aec6-3dcde31c8c00

R=mstarzinger@chromium.org

Review URL: https://codereview.chromium.org/426233002

git-svn-id: https://v8.googlecode.com/svn/branches/bleeding_edge@22709 ce2b1a6d-e550-0410-aec6-3dcde31c8c00