[turbofan] First version of loop analysis: loop finder on the soup of nodes.

[turbofan] First version of loop analysis: loop finder on the soup of nodes.

R=bmeurer@chromium.org
BUG=

Committed: https://crrev.com/0f619463f25b5c21d1f47e4f839d8aab34b9284e
Cr-Commit-Position: refs/heads/master@{#25837}

[Sven Panne, 2014-12-15 14:21:58]

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

[Sven Panne, 2014-12-15 14:21:59]

https://codereview.chromium.org/803993002/diff/1/src/zone-containers.h
File src/zone-containers.h (right):

https://codereview.chromium.org/803993002/diff/1/src/zone-containers.h#newcode92
src/zone-containers.h:92: struct PtrRange {
Drive-by nit-pick: If performance (i.e. the copying of the range) is not an
issue (it's just for test if I see this correctly), this class is unnecessary:
Just use the range constructor of e.g. vector. Furthermore, CheckRangeContains
is basically std:find then.

[titzer, 2014-12-15 15:39:07]

On 2014/12/15 14:21:59, Sven Panne wrote:
> https://codereview.chromium.org/803993002/diff/1/src/zone-containers.h
> File src/zone-containers.h (right):
> 
>
https://codereview.chromium.org/803993002/diff/1/src/zone-containers.h#newcode92
> src/zone-containers.h:92: struct PtrRange {
> Drive-by nit-pick: If performance (i.e. the copying of the range) is not an
> issue (it's just for test if I see this correctly), this class is unnecessary:
> Just use the range constructor of e.g. vector. Furthermore, CheckRangeContains
> is basically std:find then.

Yes, I considered doing that, but the problem is that nested loops can give rise
to worst case O(n^2) space, so that's the reason for the careful overlapping of
intervals. In graphs with 50,000 nodes and 30+ loops, it that could be extreme
:)

[Benedikt Meurer, 2014-12-16 06:10:26]

First round of comments. Looking good, although the tests blow my mind... :-)

https://codereview.chromium.org/803993002/diff/1/src/compiler/loop-analysis.cc
File src/compiler/loop-analysis.cc (right):

https://codereview.chromium.org/803993002/diff/1/src/compiler/loop-analysis.c...
src/compiler/loop-analysis.cc:255: int count = 0;
s/int/size_t/

https://codereview.chromium.org/803993002/diff/1/src/compiler/loop-analysis.c...
src/compiler/loop-analysis.cc:298: int count = 0;
s/int/size_t/

https://codereview.chromium.org/803993002/diff/1/src/compiler/loop-analysis.c...
src/compiler/loop-analysis.cc:328: static_cast<uint8_t>(loop_num);
Please add a TODO here to ensure that this static_cast is not overlooked when
the restriction on loop_num is gone.

https://codereview.chromium.org/803993002/diff/1/src/compiler/loop-analysis.c...
src/compiler/loop-analysis.cc:336: static_cast<uint8_t>(loop_num);
Please add a TODO here to ensure that this static_cast is not overlooked when
the restriction on loop_num is gone.

https://codereview.chromium.org/803993002/diff/1/src/compiler/loop-analysis.h
File src/compiler/loop-analysis.h (right):

https://codereview.chromium.org/803993002/diff/1/src/compiler/loop-analysis.h...
src/compiler/loop-analysis.h:32: Loop* parent() { return parent_; }
Nit: const.

https://codereview.chromium.org/803993002/diff/1/src/compiler/loop-analysis.h...
src/compiler/loop-analysis.h:34: size_t HeaderSize() { return body_start_ -
header_start_; }
Nit: const.

https://codereview.chromium.org/803993002/diff/1/src/compiler/loop-analysis.h...
src/compiler/loop-analysis.h:35: size_t BodySize() { return body_end_ -
body_start_; }
Nit: const.

https://codereview.chromium.org/803993002/diff/1/src/compiler/loop-analysis.h...
src/compiler/loop-analysis.h:36: size_t TotalSize() { return body_end_ -
header_start_; }
Nit: const.

https://codereview.chromium.org/803993002/diff/1/src/compiler/loop-analysis.h...
src/compiler/loop-analysis.h:43: : parent_(NULL),
Please use type-safe nullptr instead of NULL for newly written code, in line
with the Chromium/Google style guides.

https://codereview.chromium.org/803993002/diff/1/src/compiler/loop-analysis.h...
src/compiler/loop-analysis.h:58: Loop* ContainingLoop(Node* node) {
Nit: const.

https://codereview.chromium.org/803993002/diff/1/src/compiler/loop-analysis.h...
src/compiler/loop-analysis.h:66: bool Contains(Loop* loop, Node* node) {
Nit: const.

https://codereview.chromium.org/803993002/diff/1/src/compiler/loop-analysis.h...
src/compiler/loop-analysis.h:77: int LoopNum(Loop* loop) {
Nit: const.

https://codereview.chromium.org/803993002/diff/1/src/compiler/loop-analysis.h...
src/compiler/loop-analysis.h:77: int LoopNum(Loop* loop) {
Nit: const.

https://codereview.chromium.org/803993002/diff/1/src/zone-containers.h
File src/zone-containers.h (right):

https://codereview.chromium.org/803993002/diff/1/src/zone-containers.h#newcode92
src/zone-containers.h:92: struct PtrRange {
Ok, I see the reason to have this class in here, but it should be (a) a real STL
compatible class and (b) not in zone-containers.h as it has nothing to with
Zone. I.e.

template <typename Iterator>
class iterator_range {
 public:
  typedef Iterator iterator;
  typedef Iterator const_iterator;
  typedef std::iterator_traits<Iterator>::difference_type difference_type;

  template <typename Iterator2>
  iterator_range(Iterator2 begin, Iterator2 end) : begin_(begin), end_(end) {}

  const_iterator begin() const { return begin_; }
  const_iterator end() const { return end_; }

 private:
  const_iterator begin_ const;
  const_iterator end_ const;
};

Not sure where to put it tho. Maybe introduce some stl-utils or stl-support
header.

https://codereview.chromium.org/803993002/diff/1/test/cctest/compiler/test-lo...
File test/cctest/compiler/test-loop-analysis.cc (right):

https://codereview.chromium.org/803993002/diff/1/test/cctest/compiler/test-lo...
test/cctest/compiler/test-loop-analysis.cc:156: void
CheckRangeContains(PtrRange<Node*> range, Node* node) {
As Sven mentioned, this is just std::find().

[titzer, 2014-12-16 07:55:10]

https://codereview.chromium.org/803993002/diff/1/src/compiler/loop-analysis.cc
File src/compiler/loop-analysis.cc (right):

https://codereview.chromium.org/803993002/diff/1/src/compiler/loop-analysis.c...
src/compiler/loop-analysis.cc:255: int count = 0;
On 2014/12/16 06:10:25, Benedikt Meurer wrote:
> s/int/size_t/

Done.

https://codereview.chromium.org/803993002/diff/1/src/compiler/loop-analysis.c...
src/compiler/loop-analysis.cc:298: int count = 0;
On 2014/12/16 06:10:25, Benedikt Meurer wrote:
> s/int/size_t/

Done.

https://codereview.chromium.org/803993002/diff/1/src/compiler/loop-analysis.c...
src/compiler/loop-analysis.cc:328: static_cast<uint8_t>(loop_num);
On 2014/12/16 06:10:25, Benedikt Meurer wrote:
> Please add a TODO here to ensure that this static_cast is not overlooked when
> the restriction on loop_num is gone.

Done.

https://codereview.chromium.org/803993002/diff/1/src/compiler/loop-analysis.c...
src/compiler/loop-analysis.cc:336: static_cast<uint8_t>(loop_num);
On 2014/12/16 06:10:25, Benedikt Meurer wrote:
> Please add a TODO here to ensure that this static_cast is not overlooked when
> the restriction on loop_num is gone.

Done.

https://codereview.chromium.org/803993002/diff/1/src/compiler/loop-analysis.h
File src/compiler/loop-analysis.h (right):

https://codereview.chromium.org/803993002/diff/1/src/compiler/loop-analysis.h...
src/compiler/loop-analysis.h:32: Loop* parent() { return parent_; }
On 2014/12/16 06:10:25, Benedikt Meurer wrote:
> Nit: const.

Done.

https://codereview.chromium.org/803993002/diff/1/src/compiler/loop-analysis.h...
src/compiler/loop-analysis.h:34: size_t HeaderSize() { return body_start_ -
header_start_; }
On 2014/12/16 06:10:25, Benedikt Meurer wrote:
> Nit: const.

Done.

https://codereview.chromium.org/803993002/diff/1/src/compiler/loop-analysis.h...
src/compiler/loop-analysis.h:35: size_t BodySize() { return body_end_ -
body_start_; }
On 2014/12/16 06:10:25, Benedikt Meurer wrote:
> Nit: const.

Done.

https://codereview.chromium.org/803993002/diff/1/src/compiler/loop-analysis.h...
src/compiler/loop-analysis.h:36: size_t TotalSize() { return body_end_ -
header_start_; }
On 2014/12/16 06:10:25, Benedikt Meurer wrote:
> Nit: const.

Done.

https://codereview.chromium.org/803993002/diff/1/src/compiler/loop-analysis.h...
src/compiler/loop-analysis.h:43: : parent_(NULL),
On 2014/12/16 06:10:25, Benedikt Meurer wrote:
> Please use type-safe nullptr instead of NULL for newly written code, in line
> with the Chromium/Google style guides.

Done.

https://codereview.chromium.org/803993002/diff/1/src/compiler/loop-analysis.h...
src/compiler/loop-analysis.h:58: Loop* ContainingLoop(Node* node) {
On 2014/12/16 06:10:25, Benedikt Meurer wrote:
> Nit: const.

Const starts to spread like a virus from this site, so I'll skip this one if you
don't mind.

https://codereview.chromium.org/803993002/diff/1/src/compiler/loop-analysis.h...
src/compiler/loop-analysis.h:66: bool Contains(Loop* loop, Node* node) {
On 2014/12/16 06:10:25, Benedikt Meurer wrote:
> Nit: const.

Same as above.

https://codereview.chromium.org/803993002/diff/1/src/compiler/loop-analysis.h...
src/compiler/loop-analysis.h:77: int LoopNum(Loop* loop) {
On 2014/12/16 06:10:25, Benedikt Meurer wrote:
> Nit: const.

Done.

https://codereview.chromium.org/803993002/diff/1/src/compiler/loop-analysis.h...
src/compiler/loop-analysis.h:77: int LoopNum(Loop* loop) {
On 2014/12/16 06:10:25, Benedikt Meurer wrote:
> Nit: const.

Done.

https://codereview.chromium.org/803993002/diff/1/src/zone-containers.h
File src/zone-containers.h (right):

https://codereview.chromium.org/803993002/diff/1/src/zone-containers.h#newcode92
src/zone-containers.h:92: struct PtrRange {
On 2014/12/16 06:10:25, Benedikt Meurer wrote:
> Ok, I see the reason to have this class in here, but it should be (a) a real
STL
> compatible class and (b) not in zone-containers.h as it has nothing to with
> Zone. I.e.
> 
> template <typename Iterator>
> class iterator_range {
>  public:
>   typedef Iterator iterator;
>   typedef Iterator const_iterator;
>   typedef std::iterator_traits<Iterator>::difference_type difference_type;
> 
>   template <typename Iterator2>
>   iterator_range(Iterator2 begin, Iterator2 end) : begin_(begin), end_(end) {}
> 
>   const_iterator begin() const { return begin_; }
>   const_iterator end() const { return end_; }
> 
>  private:
>   const_iterator begin_ const;
>   const_iterator end_ const;
> };
> 
> Not sure where to put it tho. Maybe introduce some stl-utils or stl-support
> header.

Using base::iterator_range now.

https://codereview.chromium.org/803993002/diff/1/test/cctest/compiler/test-lo...
File test/cctest/compiler/test-loop-analysis.cc (right):

https://codereview.chromium.org/803993002/diff/1/test/cctest/compiler/test-lo...
test/cctest/compiler/test-loop-analysis.cc:156: void
CheckRangeContains(PtrRange<Node*> range, Node* node) {
On 2014/12/16 06:10:25, Benedikt Meurer wrote:
> As Sven mentioned, this is just std::find().

Done.

[Benedikt Meurer, 2014-12-16 08:09:33]

The CQ bit was checked by bmeurer@chromium.org

[Benedikt Meurer, 2014-12-16 08:09:33]

lgtm

[commit-bot: I haz the power, 2014-12-16 08:10:36]

CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/803993002/40001

[commit-bot: I haz the power, 2014-12-16 08:12:26]

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

[commit-bot: I haz the power, 2014-12-16 08:12:27]

Try jobs failed on following builders:
  v8_linux_arm64_rel on tryserver.v8
(http://build.chromium.org/p/tryserver.v8/builders/v8_linux_arm64_rel/builds/1783)

[titzer, 2014-12-16 09:08:22]

The CQ bit was checked by titzer@chromium.org

[commit-bot: I haz the power, 2014-12-16 09:08:56]

CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/803993002/80001

[commit-bot: I haz the power, 2014-12-16 09:36:24]

Committed patchset #5 (id:80001)

[commit-bot: I haz the power, 2014-12-17 10:14:03]

Patchset 5 (id:??) landed as
https://crrev.com/0f619463f25b5c21d1f47e4f839d8aab34b9284e
Cr-Commit-Position: refs/heads/master@{#25837}