Subzero: Improve LoopAnalyzer Interface

Improve LoopAnalyzer Interface

Make LoopAnalyzer compute loop bodies and depth only.
Move the logic for finding out loop headers and pre-headers to LoopInfo, which provides a visitor to iterate over the loops and easy access to the information.
This does not change the core algorithm.

BUG=None
R=jpp@chromium.org, stichnot@chromium.org

Committed: https://gerrit.chromium.org/gerrit/gitweb?p=native_client/pnacl-subzero.git;a=commit;h=adf352bcfc24b22b75945ed45b1024943af3a690

[manasijm, 2016-07-15 19:37:40]

Description was changed from

==========
Improve LoopAnalyzer Interface

BUG=None
==========

to

==========
Improve LoopAnalyzer Interface

Make LoopAnalyzer compute loop bodies and depth only.
Move the logic for finding out loop headers and pre-headers to LoopInfo, which
provides a visitor to iterate over the loops and easy access to the information.
This does not change the core algorithm.

BUG=None
==========

[manasijm, 2016-07-15 19:37:40]

manasijm@google.com changed reviewers:
+ eholk@chromium.org, jpp@chromium.org, kschimpf@google.com,
stichnot@chromium.org

[John, 2016-07-15 21:13:30]

https://codereview.chromium.org/2149803005/diff/1/src/IceCfg.cpp
File src/IceCfg.cpp (right):

https://codereview.chromium.org/2149803005/diff/1/src/IceCfg.cpp#newcode646
src/IceCfg.cpp:646: Loops.forEachLoop([&](SizeT HeaderIndex, const
CfgUnorderedSet<SizeT> &Body) {
no default capture by ref.

also, can you do something like this instead?

for (set<BasicBlocks>* loop : Loops.allLoops()) {
}

https://codereview.chromium.org/2149803005/diff/1/src/IceLoopAnalyzer.cpp
File src/IceLoopAnalyzer.cpp (right):

https://codereview.chromium.org/2149803005/diff/1/src/IceLoopAnalyzer.cpp#new...
src/IceLoopAnalyzer.cpp:152: Loops.push_back(LoopNodes);
this is awfully inefficient! you're copying LoopNodes here, and you probably
don't want to do that. Instead, do

Loops.emplace_back(std::move(LoopNode));

Alternatively (I prefer this approach), do

Loop.emplace_back({});  // pushes a new, empty loop in Loops
auto* LoopNodes = &Loop.back();

and then s/LoopNodes./LoopNodes->/

https://codereview.chromium.org/2149803005/diff/1/src/IceLoopAnalyzer.cpp#new...
src/IceLoopAnalyzer.cpp:160: void LoopAnalyzer::LoopInfo::computeLoopMetaData()
{
Why do you need this method? where was it defined before?

https://codereview.chromium.org/2149803005/diff/1/src/IceLoopAnalyzer.h
File src/IceLoopAnalyzer.h (left):

https://codereview.chromium.org/2149803005/diff/1/src/IceLoopAnalyzer.h#oldco...
src/IceLoopAnalyzer.h:23: class LoopAnalyzer {
OK, you opened pandora's box... :)

This class is really a function. Why? Well, this object has very little state of
its own, and its use

LoopAnalyzer(this).getLoopInfo()

can be replaced by

findLoopsInCfg(this);

But this is really just

this->findLoops();

If I were to refactor this code, I would get rid of this class (LoopAnalyzer),
and keep the LoopInfo here.

https://codereview.chromium.org/2149803005/diff/1/src/IceLoopAnalyzer.h
File src/IceLoopAnalyzer.h (right):

https://codereview.chromium.org/2149803005/diff/1/src/IceLoopAnalyzer.h#newco...
src/IceLoopAnalyzer.h:48: template <typename F> void forEachLoop(F Callback) {
no need for this: just create a getter for LoopIndexForHeader (see the comment
in IceCfg.h)

[Jim Stichnoth, 2016-07-15 22:14:33]

https://codereview.chromium.org/2149803005/diff/1/src/IceCfg.h
File src/IceCfg.h (right):

https://codereview.chromium.org/2149803005/diff/1/src/IceCfg.h#newcode25
src/IceCfg.h:25: #include "IceLoopAnalyzer.h"
alphabetize includes if possible

https://codereview.chromium.org/2149803005/diff/1/src/IceLoopAnalyzer.cpp
File src/IceLoopAnalyzer.cpp (right):

https://codereview.chromium.org/2149803005/diff/1/src/IceLoopAnalyzer.cpp#new...
src/IceLoopAnalyzer.cpp:192: //       CfgNode *Cur =
Func->getNodes()[NodeIndex];
Remove this?

[John, 2016-07-18 15:25:37]

https://codereview.chromium.org/2149803005/diff/1/src/IceLoopAnalyzer.cpp
File src/IceLoopAnalyzer.cpp (right):

https://codereview.chromium.org/2149803005/diff/1/src/IceLoopAnalyzer.cpp#new...
src/IceLoopAnalyzer.cpp:160: void LoopAnalyzer::LoopInfo::computeLoopMetaData()
{
On 2016/07/15 21:13:30, John wrote:
> Why do you need this method? where was it defined before?

nevermind.

https://codereview.chromium.org/2149803005/diff/1/src/IceLoopAnalyzer.h
File src/IceLoopAnalyzer.h (right):

https://codereview.chromium.org/2149803005/diff/1/src/IceLoopAnalyzer.h#newco...
src/IceLoopAnalyzer.h:43: LoopInfo(Cfg *Func, const
CfgVector<CfgUnorderedSet<SizeT>> Loops)
A nice way to decrease memory usage: pass Loops by *, and then std::swap it.

https://codereview.chromium.org/2149803005/diff/1/src/IceLoopAnalyzer.h#newco...
src/IceLoopAnalyzer.h:53: CfgNode *getHeader(CfgNode *Node);
getHeader, and getBody aren't used anywhere. remove them?

https://codereview.chromium.org/2149803005/diff/1/src/IceLoopAnalyzer.h#newco...
src/IceLoopAnalyzer.h:60: CfgVector<CfgUnorderedSet<SizeT>> Loops;
How about changing this vector to be a vector of structs

struct Loop {
  const CfgUnorderedSet<SizeT> Blocks;
  CfgNode const *Header;
  CfgNode const *PreHeader;
  Loop(CfgUnorderedSet<SizeT> &&B, CfgNode *H, CfgNode *P) : Blocks(B),
Header(H), PreHeader(P) {}
}

If you do this, and you change the constructor parameter to take a CfgVector*,
then you can initialize the Loops vector as following:

LoopInfo::LoopInfo(Cfg *Func, CfgVector<CfgUnorderedSet<SizeT>> *L) {
  L->reserve(L->size());
  std::sort(Loops->begin(), Loops->end(), ...);
  for (auto *Loop : Loops) {
    auto *Header = findHeader(Loop);
    auto *PreHeader = findPreHeader(Header);
    Loops.emplace_back(std::move(*Loop), Header, PreHeader);
  }
}

But now, your CfgVector<Loop> Loops member contains everything you need to know
about your loops. Therefore, you don't really need to create a

class LoopInfo {
 public:
  LoopInfo(Cfg *Func, CfgVector<CfgUnorderedSet<SizeT>> L);
  const CfgVector<Loop> &getLoops();

 private:
  CfgVector<Loop> Loops;
};

This is really bad OOP. Your interface really is

CfgVector<Loop> computeLoopInfo(CfgVector<CfgUnorderedSet<SizeT>> L) {
  CfgVector<Loop> Loops;

  // same as LoopInfo::LoopInfo above

  return Loops;
}

[manasijm, 2016-07-18 22:27:47]

https://codereview.chromium.org/2149803005/diff/1/src/IceCfg.cpp
File src/IceCfg.cpp (right):

https://codereview.chromium.org/2149803005/diff/1/src/IceCfg.cpp#newcode646
src/IceCfg.cpp:646: Loops.forEachLoop([&](SizeT HeaderIndex, const
CfgUnorderedSet<SizeT> &Body) {
On 2016/07/15 21:13:30, John wrote:
> no default capture by ref.
> 
> also, can you do something like this instead?
> 
> for (set<BasicBlocks>* loop : Loops.allLoops()) {
> }

Done.

https://codereview.chromium.org/2149803005/diff/1/src/IceCfg.h
File src/IceCfg.h (right):

https://codereview.chromium.org/2149803005/diff/1/src/IceCfg.h#newcode25
src/IceCfg.h:25: #include "IceLoopAnalyzer.h"
On 2016/07/15 22:14:33, stichnot wrote:
> alphabetize includes if possible

Done.

https://codereview.chromium.org/2149803005/diff/1/src/IceLoopAnalyzer.cpp
File src/IceLoopAnalyzer.cpp (right):

https://codereview.chromium.org/2149803005/diff/1/src/IceLoopAnalyzer.cpp#new...
src/IceLoopAnalyzer.cpp:160: void LoopAnalyzer::LoopInfo::computeLoopMetaData()
{
On 2016/07/15 21:13:30, John wrote:
> Why do you need this method? where was it defined before?

It was not there.
I am computing headers and pre-headers (if any) for loops here.

https://codereview.chromium.org/2149803005/diff/1/src/IceLoopAnalyzer.cpp#new...
src/IceLoopAnalyzer.cpp:192: //       CfgNode *Cur =
Func->getNodes()[NodeIndex];
On 2016/07/15 22:14:33, stichnot wrote:
> Remove this?

Done.

https://codereview.chromium.org/2149803005/diff/1/src/IceLoopAnalyzer.h
File src/IceLoopAnalyzer.h (right):

https://codereview.chromium.org/2149803005/diff/1/src/IceLoopAnalyzer.h#newco...
src/IceLoopAnalyzer.h:43: LoopInfo(Cfg *Func, const
CfgVector<CfgUnorderedSet<SizeT>> Loops)
Should be 'moved' by default in new implementation.

https://codereview.chromium.org/2149803005/diff/1/src/IceLoopAnalyzer.h#newco...
src/IceLoopAnalyzer.h:48: template <typename F> void forEachLoop(F Callback) {
On 2016/07/15 21:13:30, John wrote:
> no need for this: just create a getter for LoopIndexForHeader (see the comment
> in IceCfg.h)

Done.

https://codereview.chromium.org/2149803005/diff/1/src/IceLoopAnalyzer.h#newco...
src/IceLoopAnalyzer.h:53: CfgNode *getHeader(CfgNode *Node);
On 2016/07/18 15:25:36, John wrote:
> getHeader, and getBody aren't used anywhere. remove them?

Done.

[John, 2016-07-19 16:13:12]

lgtm

see if Jim's OK as well

https://codereview.chromium.org/2149803005/diff/20001/src/IceLoopAnalyzer.h
File src/IceLoopAnalyzer.h (right):

https://codereview.chromium.org/2149803005/diff/20001/src/IceLoopAnalyzer.h#n...
src/IceLoopAnalyzer.h:26: CfgUnorderedSet<SizeT> Body; // Node IDs
add const to the members here. I never know if you need to write

const CfgNode *

or

CfgNode const*

(I believe it is the latter.)

[manasijm, 2016-07-19 20:17:02]

https://codereview.chromium.org/2149803005/diff/20001/src/IceLoopAnalyzer.h
File src/IceLoopAnalyzer.h (right):

https://codereview.chromium.org/2149803005/diff/20001/src/IceLoopAnalyzer.h#n...
src/IceLoopAnalyzer.h:26: CfgUnorderedSet<SizeT> Body; // Node IDs
On 2016/07/19 16:13:12, John wrote:
> add const to the members here. I never know if you need to write
> 
> const CfgNode *
> 
> or
> 
> CfgNode const*
> 
> (I believe it is the latter.)
It seems to be 
CfgNode *const
But:
LoopInfo = ComputeLoopInfo(this)
This needs the = operator which is deleted if I declare the pointer constant.

[Jim Stichnoth, 2016-07-19 20:22:56]

otherwise lgtm

https://codereview.chromium.org/2149803005/diff/20001/src/IceLoopAnalyzer.cpp
File src/IceLoopAnalyzer.cpp (right):

https://codereview.chromium.org/2149803005/diff/20001/src/IceLoopAnalyzer.cpp...
src/IceLoopAnalyzer.cpp:24: LoopAnalyzer() = default;
Also delete or "default" the default copy ctor and assignment operator.

[manasijm, 2016-07-19 20:31:39]

Description was changed from

==========
Improve LoopAnalyzer Interface

Make LoopAnalyzer compute loop bodies and depth only.
Move the logic for finding out loop headers and pre-headers to LoopInfo, which
provides a visitor to iterate over the loops and easy access to the information.
This does not change the core algorithm.

BUG=None
==========

to

==========
Improve LoopAnalyzer Interface

Make LoopAnalyzer compute loop bodies and depth only.
Move the logic for finding out loop headers and pre-headers to LoopInfo, which
provides a visitor to iterate over the loops and easy access to the information.
This does not change the core algorithm.

BUG=None
R=jpp@chromium.org, stichnot@chromium.org

Committed:
https://gerrit.chromium.org/gerrit/gitweb?p=native_client/pnacl-subzero.git;a...
==========

[manasijm, 2016-07-19 20:31:40]

Committed patchset #2 (id:20001) manually as
adf352bcfc24b22b75945ed45b1024943af3a690 (presubmit successful).