[ignition] Replace branch+loop analysis with a single pass

[ignition] Replace branch+loop analysis with a single pass

Now that we have a JumpLoop bytecode, we can heavily simplify the
branch/loop analysis by assuming that only JumpLoop bytecodes are
backwards edges, and performing the loop analysis as a single
(backwards) pass.

This allows us to get rid of the branch analysis entirely, and builds a
framework to do liveness analysis in the same pass.

Committed: https://crrev.com/292c4a0a2a45b14c86ba911339c2af91a3e2b647
Cr-Commit-Position: refs/heads/master@{#41194}

[Leszek Swirski, 2016-11-21 16:32:47]

The CQ bit was checked by leszeks@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2016-11-21 16:32:50]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2016-11-21 16:35:20]

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

[commit-bot: I haz the power, 2016-11-21 16:35:21]

Dry run: Try jobs failed on following builders:
  v8_linux_gcc_compile_rel on master.tryserver.v8 (JOB_FAILED,
http://build.chromium.org/p/tryserver.v8/builders/v8_linux_gcc_compile_rel/bu...)
  v8_linux_nodcheck_rel_ng on master.tryserver.v8 (JOB_FAILED,
http://build.chromium.org/p/tryserver.v8/builders/v8_linux_nodcheck_rel_ng/bu...)
  v8_mac_rel_ng on master.tryserver.v8 (JOB_FAILED,
http://build.chromium.org/p/tryserver.v8/builders/v8_mac_rel_ng/builds/12909)
  v8_win_rel_ng on master.tryserver.v8 (JOB_FAILED,
http://build.chromium.org/p/tryserver.v8/builders/v8_win_rel_ng/builds/18240)

[Leszek Swirski, 2016-11-21 16:56:15]

The CQ bit was checked by leszeks@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2016-11-21 16:56:20]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[Leszek Swirski, 2016-11-21 17:07:09]

leszeks@chromium.org changed reviewers:
+ rmcilroy@chromium.org

[Leszek Swirski, 2016-11-21 17:07:09]

Hi Ross,

Here's the CL simplifying the branch+loop analysis into a single reverse loop
analysis pass. I've also taken the opportunity to annotate it with ascii art,
because it took me way too long to figure out what it was doing.

[commit-bot: I haz the power, 2016-11-21 17:21:35]

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

[commit-bot: I haz the power, 2016-11-21 17:21:35]

Dry run: This issue passed the CQ dry run.

[rmcilroy, 2016-11-22 11:02:06]

rmcilroy@chromium.org changed reviewers:
+ jarin@chromium.org

[rmcilroy, 2016-11-22 11:02:07]

LGTM

Jaro, could you take a look please?

https://codereview.chromium.org/2519983002/diff/20001/src/compiler/bytecode-a...
File src/compiler/bytecode-analysis.h (right):

https://codereview.chromium.org/2519983002/diff/20001/src/compiler/bytecode-a...
src/compiler/bytecode-analysis.h:22: // Analyze the bytecodes to find the branch
sites and their
nit - this comment should be updated to talk about loops rather than branch
sites and targets.

https://codereview.chromium.org/2519983002/diff/20001/src/compiler/bytecode-g...
File src/compiler/bytecode-graph-builder.cc (right):

https://codereview.chromium.org/2519983002/diff/20001/src/compiler/bytecode-g...
src/compiler/bytecode-graph-builder.cc:1947: // branch, otherwise there will not
be a proper loop header available.
nit - update comment

[Jarin, 2016-11-22 11:59:18]

lgtm, thanks for the pictures and explanations.

https://codereview.chromium.org/2519983002/diff/20001/src/compiler/bytecode-a...
File src/compiler/bytecode-analysis.cc (right):

https://codereview.chromium.org/2519983002/diff/20001/src/compiler/bytecode-a...
src/compiler/bytecode-analysis.cc:42: DCHECK(loop_stack_.top() < loop_header);
Oh, we do not have multiple back-edges anymore?

[Leszek Swirski, 2016-11-22 17:39:03]

https://codereview.chromium.org/2519983002/diff/20001/src/compiler/bytecode-a...
File src/compiler/bytecode-analysis.cc (right):

https://codereview.chromium.org/2519983002/diff/20001/src/compiler/bytecode-a...
src/compiler/bytecode-analysis.cc:42: DCHECK(loop_stack_.top() < loop_header);
On 2016/11/22 11:59:18, Jarin wrote:
> Oh, we do not have multiple back-edges anymore?

Not anymore, ever since we added the JumpLoop bytecode. Continues jump to the
end of the loop now.

https://codereview.chromium.org/2519983002/diff/20001/src/compiler/bytecode-a...
File src/compiler/bytecode-analysis.h (right):

https://codereview.chromium.org/2519983002/diff/20001/src/compiler/bytecode-a...
src/compiler/bytecode-analysis.h:22: // Analyze the bytecodes to find the branch
sites and their
On 2016/11/22 11:02:07, rmcilroy wrote:
> nit - this comment should be updated to talk about loops rather than branch
> sites and targets.

Done.

https://codereview.chromium.org/2519983002/diff/20001/src/compiler/bytecode-g...
File src/compiler/bytecode-graph-builder.cc (right):

https://codereview.chromium.org/2519983002/diff/20001/src/compiler/bytecode-g...
src/compiler/bytecode-graph-builder.cc:1947: // branch, otherwise there will not
be a proper loop header available.
On 2016/11/22 11:02:07, rmcilroy wrote:
> nit - update comment

Done.

[Leszek Swirski, 2016-11-22 17:39:16]

The CQ bit was checked by leszeks@chromium.org

[Leszek Swirski, 2016-11-22 17:39:17]

The patchset sent to the CQ was uploaded after l-g-t-m from jarin@chromium.org,
rmcilroy@chromium.org
Link to the patchset: https://codereview.chromium.org/2519983002/#ps40001
(title: "Update comments")

[commit-bot: I haz the power, 2016-11-22 17:39:20]

CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2016-11-22 18:05:04]

CQ is committing da patch.

Bot data: {"patchset_id": 40001, "attempt_start_ts": 1479836356964600,
"parent_rev": "1e666f8819c0932582767ea0ed2c3ec5363cf891", "commit_rev":
"01a97a3bae178977d69e2fab09034c27eadaab41"}

[commit-bot: I haz the power, 2016-11-22 18:05:09]

Committed patchset #3 (id:40001)

[commit-bot: I haz the power, 2016-11-22 18:05:35]

Description was changed from

==========
[ignition] Replace branch+loop analysis with a single pass

Now that we have a JumpLoop bytecode, we can heavily simplify the
branch/loop analysis by assuming that only JumpLoop bytecodes are
backwards edges, and performing the loop analysis as a single
(backwards) pass.

This allows us to get rid of the branch analysis entirely, and builds a
framework to do liveness analysis in the same pass.
==========

to

==========
[ignition] Replace branch+loop analysis with a single pass

Now that we have a JumpLoop bytecode, we can heavily simplify the
branch/loop analysis by assuming that only JumpLoop bytecodes are
backwards edges, and performing the loop analysis as a single
(backwards) pass.

This allows us to get rid of the branch analysis entirely, and builds a
framework to do liveness analysis in the same pass.

Committed: https://crrev.com/292c4a0a2a45b14c86ba911339c2af91a3e2b647
Cr-Commit-Position: refs/heads/master@{#41194}
==========

[commit-bot: I haz the power, 2016-11-22 18:05:36]

Patchset 3 (id:??) landed as
https://crrev.com/292c4a0a2a45b14c86ba911339c2af91a3e2b647
Cr-Commit-Position: refs/heads/master@{#41194}