Compute the loop nest depth of each CfgNode and weight Variables by it.

This improves the variable use weight by taking into account use in loops. It
further improves spec2k performance and fixes the regression in ammp. Loops are
identified using an extension to Tarjan's algorithm.

BUG=
R=stichnot@chromium.org

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

[ascull, 2015-08-31 21:59:43]

I haven't done a complete benchmarking but it seems to be over 3% improvement on
top of the previous 10% Jim measured. The regression in ammp seems to be fixed
and there is possibly small improvement too.

My test cases are quite simple ones at the moment. I've been thinking about some
more complicated ones such as nested loops overlapping each other but am unsure
whether they are worth considering?

I have used a goto to continue an outer loop which I consider to be a sane use
as it is not spaghetti code and is clearly explained by the label name and a
comment. But I know some people are strongly averse to goto's use, how do you
feel?

[ascull, 2015-09-01 18:33:17]

ascull@google.com changed reviewers:
+ jvoung@chromium.org, stichnot@chromium.org

[ascull, 2015-09-01 18:33:18]

I just realized I only published to myself *facepalm*. I wondered why noone had
commented!

[jvoung (off chromium), 2015-09-01 18:56:18]

Yes, it helps to set the reviewers ;-)

https://codereview.chromium.org/1318553003/diff/20001/src/IceCfg.cpp
File src/IceCfg.cpp (right):

https://codereview.chromium.org/1318553003/diff/20001/src/IceCfg.cpp#newcode465
src/IceCfg.cpp:465: // Use Tarjn's strongly connected components algorithm to
identify outermost to
Tarjan's

https://codereview.chromium.org/1318553003/diff/20001/src/IceCfg.cpp#newcode500
src/IceCfg.cpp:500: bool deleted = false;
capitalize deleted to follow code style

https://codereview.chromium.org/1318553003/diff/20001/src/IceCfg.cpp#newcode512
src/IceCfg.cpp:512: // stack which doesn not support reserving (or bulk erasure
used below).
doesn -> doesn't

https://codereview.chromium.org/1318553003/diff/20001/src/IceCfg.cpp#newcode525
src/IceCfg.cpp:525: index_t NextIndex = 1;
nit: How about UndefinedIndex + 1, to ensure the initial value is different?  1
is fine too.

https://codereview.chromium.org/1318553003/diff/20001/src/IceCfg.cpp#newcode527
src/IceCfg.cpp:527: Node.reset();
Wonder if you should add an Ice timer for this whole function to profile it.
Tarjan's is O(V+E), but this resets some number of times depending on the loop
nesting.

https://codereview.chromium.org/1318553003/diff/20001/src/IceCfg.cpp#newcode568
src/IceCfg.cpp:568: goto continue_work_loop; // continue outer loop
You might be able to get away without a goto, if you make the loop body a
function, and then return; instead of goto.

Not sure how many parameters you'll have to pass around though, so that may be
messy. On the other hand, the loop body is pretty deeply nested so that may be a
reason to separate it out into a function.

https://codereview.chromium.org/1318553003/diff/20001/src/IceCfg.cpp#newcode577
src/IceCfg.cpp:577: // may be reentrancy but we ignore that here.
What do you mean by reentrancy here? Branches from local labels?

https://codereview.chromium.org/1318553003/diff/20001/src/IceTargetLoweringX8...
File src/IceTargetLoweringX86BaseImpl.h (right):

https://codereview.chromium.org/1318553003/diff/20001/src/IceTargetLoweringX8...
src/IceTargetLoweringX86BaseImpl.h:331: // code.
Some new nodes are created later, but I suppose those don't require the loop
analysis information.

https://codereview.chromium.org/1318553003/diff/20001/src/IceTargetLoweringX8...
src/IceTargetLoweringX86BaseImpl.h:378: // liveness analysis. Loops must be
identified before livness to variable use
"livness"

something sounds odd about "Loops must be identified before liveness to variable
use weights are correct"

https://codereview.chromium.org/1318553003/diff/20001/tests_lit/llvm2ice_test...
File tests_lit/llvm2ice_tests/loop-nest-depth.ll (right):

https://codereview.chromium.org/1318553003/diff/20001/tests_lit/llvm2ice_test...
tests_lit/llvm2ice_tests/loop-nest-depth.ll:2: 
Can you check that this works with "make -f Makefile.standalone MINIMAL=1
check-lit"? I think it:

"REQUIRES: allow_dump"

https://codereview.chromium.org/1318553003/diff/20001/tests_lit/llvm2ice_test...
tests_lit/llvm2ice_tests/loop-nest-depth.ll:7: define void @test_single_loop(i1
%a) {
Hmm, technically PNaCl does not allow i1 parameters, only i32 and larger (i.e.,
i64):
https://developer.chrome.com/native-client/reference/pnacl-bitcode-abi#scalar...
(this is because most targets have 32-bit wide stack slots or parameter
registers only, and you'd have to otherwise specify whether to sign extend or
zero extend to fill it up).

So I worry that the bitcode reader could become stricter and break on this test.

You could trunc i32 %a to i1 early in the function though.

Similar below.

https://codereview.chromium.org/1318553003/diff/20001/tests_lit/llvm2ice_test...
tests_lit/llvm2ice_tests/loop-nest-depth.ll:19: 
Can you still CHECK-LABEL: test_single_loop

to help FileCheck partition the log?

https://codereview.chromium.org/1318553003/diff/20001/tests_lit/llvm2ice_test...
tests_lit/llvm2ice_tests/loop-nest-depth.ll:25: 
Could add a "negative" test -- some non-loopy code with branches (like a
diamond).

Also, what about something irreducible like example d in:
https://en.wikipedia.org/wiki/Control_flow_graph#Definition

or something with multiple exits like c?

[Jim Stichnoth, 2015-09-01 22:17:38]

https://codereview.chromium.org/1318553003/diff/20001/src/IceCfg.cpp
File src/IceCfg.cpp (right):

https://codereview.chromium.org/1318553003/diff/20001/src/IceCfg.cpp#newcode65
src/IceCfg.cpp:65: CfgNode *Node = CfgNode::create(this, LabelIndex);
May want to document here that LoopNestDepth may not be valid if makeNode() runs
after computeLoopNestDepth().

https://codereview.chromium.org/1318553003/diff/20001/src/IceCfg.cpp#newcode472
src/IceCfg.cpp:472: void Cfg::computeLoopNestDepth() {
Add a TimerMarker here (and add a new marker type in IceTimerTree.def).

https://codereview.chromium.org/1318553003/diff/20001/src/IceCfg.cpp#newcode473
src/IceCfg.cpp:473: using index_t = uint32_t;
Type names should be capitalized per LLVM coding style.

https://codereview.chromium.org/1318553003/diff/20001/src/IceCfg.cpp#newcode476
src/IceCfg.cpp:476: struct LoopNode {
I think if you are defining methods, you should call it a class instead of
struct.

https://codereview.chromium.org/1318553003/diff/20001/src/IceCfg.cpp#newcode496
src/IceCfg.cpp:496: NodeList::const_iterator Succ;
Initialize members in the ctor or in the same way as "deleted"

https://codereview.chromium.org/1318553003/diff/20001/src/IceCfg.cpp#newcode521
src/IceCfg.cpp:521: size_t NumDeletedNodes = 0;
SizeT

or, if you object to that,
std::vector<LoopNode, CfgLocalAllocator<LoopNode>>::size_type
:)

https://codereview.chromium.org/1318553003/diff/20001/src/IceCfgNode.cpp
File src/IceCfgNode.cpp (right):

https://codereview.chromium.org/1318553003/diff/20001/src/IceCfgNode.cpp#newc...
src/IceCfgNode.cpp:220: CfgNode *NewNode = Func->makeNode();
Here I think you could set NewNode->LoopNestDepth = this->getLoopNestDepth().

Though I'm not sure whether you should use this, or Pred, or min(this,Pred), or
max(this,Pred).

https://codereview.chromium.org/1318553003/diff/20001/src/IceCfgNode.cpp#newc...
src/IceCfgNode.cpp:1187: Str << "    // LoopNestDepth = " << LoopNestDepth <<
"\n";
I suggest adding the node label - getName() - to the comment string, so that the
lit tests can be more precise in their matching.

Also, use getLoopNestDepth() instead of LoopNestDepth.

https://codereview.chromium.org/1318553003/diff/20001/src/IceCfgNode.h
File src/IceCfgNode.h (right):

https://codereview.chromium.org/1318553003/diff/20001/src/IceCfgNode.h#newcod...
src/IceCfgNode.h:117: uint32_t LoopNestDepth = 0;      /// the loop nest depth
of this node
Maybe the uint32_t should be SizeT?

https://codereview.chromium.org/1318553003/diff/20001/src/IceOperand.cpp
File src/IceOperand.cpp (right):

https://codereview.chromium.org/1318553003/diff/20001/src/IceOperand.cpp#newc...
src/IceOperand.cpp:163: constexpr uint32_t LogTypicalLoopTripCount = 3; // 2^3 =
8
nit: "Typical" implies knowledge we don't have.  I think
LogLoopTripCountEstimate would be better.

https://codereview.chromium.org/1318553003/diff/20001/src/IceOperand.cpp#newc...
src/IceOperand.cpp:164: uint32_t ThisUseWeight =
Maybe SizeT instead of uint32_t?

https://codereview.chromium.org/1318553003/diff/20001/src/IceOperand.cpp#newc...
src/IceOperand.cpp:165: 1 << std::min(Node->getLoopNestDepth() *
LogTypicalLoopTripCount, 31u);
No magic constants please. :)

CHAR_BIT * sizeof(ThisUseWeight) - 1

https://codereview.chromium.org/1318553003/diff/20001/src/IceOperand.cpp#newc...
src/IceOperand.cpp:168: UseWeight = NewWeight < UseWeight ? RegWeight::Inf - 1
How about something defining something like RegWeight::Max which is denoted as
the maximum non-infinite weight?  RegWeight::addWeight() could also be tightened
up using that.

https://codereview.chromium.org/1318553003/diff/20001/src/IceTargetLoweringX8...
File src/IceTargetLoweringX86BaseImpl.h (right):

https://codereview.chromium.org/1318553003/diff/20001/src/IceTargetLoweringX8...
src/IceTargetLoweringX86BaseImpl.h:332: // TODO: currently only used for
regalloc not expensive high level
TODO(ascull,stichnot)

https://codereview.chromium.org/1318553003/diff/20001/src/IceTargetLoweringX8...
src/IceTargetLoweringX86BaseImpl.h:378: // liveness analysis. Loops must be
identified before livness to variable use
On 2015/09/01 18:56:18, jvoung wrote:
> "livness"
> 
> something sounds odd about "Loops must be identified before liveness to
variable
> use weights are correct"

I think you mean "so variable use"?

https://codereview.chromium.org/1318553003/diff/20001/tests_lit/llvm2ice_test...
File tests_lit/llvm2ice_tests/loop-nest-depth.ll (right):

https://codereview.chromium.org/1318553003/diff/20001/tests_lit/llvm2ice_test...
tests_lit/llvm2ice_tests/loop-nest-depth.ll:6: 
I'd like to see at least one test with loops and phi instructions (into and out
of the loop) and O2.  Perhaps simple_loop.ll is good enough.

[ascull, 2015-09-03 19:52:38]

https://codereview.chromium.org/1318553003/diff/20001/src/IceCfg.cpp
File src/IceCfg.cpp (right):

https://codereview.chromium.org/1318553003/diff/20001/src/IceCfg.cpp#newcode65
src/IceCfg.cpp:65: CfgNode *Node = CfgNode::create(this, LabelIndex);
On 2015/09/01 22:17:37, stichnot wrote:
> May want to document here that LoopNestDepth may not be valid if makeNode()
runs
> after computeLoopNestDepth().

Done.

https://codereview.chromium.org/1318553003/diff/20001/src/IceCfg.cpp#newcode465
src/IceCfg.cpp:465: // Use Tarjn's strongly connected components algorithm to
identify outermost to
On 2015/09/01 18:56:18, jvoung wrote:
> Tarjan's

Done.

https://codereview.chromium.org/1318553003/diff/20001/src/IceCfg.cpp#newcode472
src/IceCfg.cpp:472: void Cfg::computeLoopNestDepth() {
On 2015/09/01 22:17:37, stichnot wrote:
> Add a TimerMarker here (and add a new marker type in IceTimerTree.def).

Done.

https://codereview.chromium.org/1318553003/diff/20001/src/IceCfg.cpp#newcode473
src/IceCfg.cpp:473: using index_t = uint32_t;
On 2015/09/01 22:17:37, stichnot wrote:
> Type names should be capitalized per LLVM coding style.

Done.

https://codereview.chromium.org/1318553003/diff/20001/src/IceCfg.cpp#newcode476
src/IceCfg.cpp:476: struct LoopNode {
On 2015/09/01 22:17:37, stichnot wrote:
> I think if you are defining methods, you should call it a class instead of
> struct.

Done.

https://codereview.chromium.org/1318553003/diff/20001/src/IceCfg.cpp#newcode496
src/IceCfg.cpp:496: NodeList::const_iterator Succ;
On 2015/09/01 22:17:37, stichnot wrote:
> Initialize members in the ctor or in the same way as "deleted"

Done.

https://codereview.chromium.org/1318553003/diff/20001/src/IceCfg.cpp#newcode500
src/IceCfg.cpp:500: bool deleted = false;
On 2015/09/01 18:56:17, jvoung wrote:
> capitalize deleted to follow code style

Done.

https://codereview.chromium.org/1318553003/diff/20001/src/IceCfg.cpp#newcode512
src/IceCfg.cpp:512: // stack which doesn not support reserving (or bulk erasure
used below).
On 2015/09/01 18:56:18, jvoung wrote:
> doesn -> doesn't

Done.

https://codereview.chromium.org/1318553003/diff/20001/src/IceCfg.cpp#newcode521
src/IceCfg.cpp:521: size_t NumDeletedNodes = 0;
On 2015/09/01 22:17:37, stichnot wrote:
> SizeT
> 
> or, if you object to that,
> std::vector<LoopNode, CfgLocalAllocator<LoopNode>>::size_type
> :)

Done.

https://codereview.chromium.org/1318553003/diff/20001/src/IceCfg.cpp#newcode525
src/IceCfg.cpp:525: index_t NextIndex = 1;
On 2015/09/01 18:56:18, jvoung wrote:
> nit: How about UndefinedIndex + 1, to ensure the initial value is different? 
1
> is fine too.

Done.

https://codereview.chromium.org/1318553003/diff/20001/src/IceCfg.cpp#newcode527
src/IceCfg.cpp:527: Node.reset();
On 2015/09/01 18:56:18, jvoung wrote:
> Wonder if you should add an Ice timer for this whole function to profile it.
> Tarjan's is O(V+E), but this resets some number of times depending on the loop
> nesting.

Done.

https://codereview.chromium.org/1318553003/diff/20001/src/IceCfg.cpp#newcode568
src/IceCfg.cpp:568: goto continue_work_loop; // continue outer loop
On 2015/09/01 18:56:18, jvoung wrote:
> You might be able to get away without a goto, if you make the loop body a
> function, and then return; instead of goto.
> 
> Not sure how many parameters you'll have to pass around though, so that may be
> messy. On the other hand, the loop body is pretty deeply nested so that may be
a
> reason to separate it out into a function.

I refactored the loop stuff out into it's own class and made this change in the
process.

https://codereview.chromium.org/1318553003/diff/20001/src/IceCfg.cpp#newcode577
src/IceCfg.cpp:577: // may be reentrancy but we ignore that here.
On 2015/09/01 18:56:18, jvoung wrote:
> What do you mean by reentrancy here? Branches from local labels?

That is what I meant, although it isn't a useful comment any more as this
analysis take place before lowering.

https://codereview.chromium.org/1318553003/diff/20001/src/IceCfgNode.cpp
File src/IceCfgNode.cpp (right):

https://codereview.chromium.org/1318553003/diff/20001/src/IceCfgNode.cpp#newc...
src/IceCfgNode.cpp:220: CfgNode *NewNode = Func->makeNode();
On 2015/09/01 22:17:37, stichnot wrote:
> Here I think you could set NewNode->LoopNestDepth = this->getLoopNestDepth().
> 
> Though I'm not sure whether you should use this, or Pred, or min(this,Pred),
or
> max(this,Pred).

Done.

https://codereview.chromium.org/1318553003/diff/20001/src/IceCfgNode.cpp#newc...
src/IceCfgNode.cpp:1187: Str << "    // LoopNestDepth = " << LoopNestDepth <<
"\n";
On 2015/09/01 22:17:37, stichnot wrote:
> I suggest adding the node label - getName() - to the comment string, so that
the
> lit tests can be more precise in their matching.
> 
> Also, use getLoopNestDepth() instead of LoopNestDepth.

Done.

https://codereview.chromium.org/1318553003/diff/20001/src/IceCfgNode.h
File src/IceCfgNode.h (right):

https://codereview.chromium.org/1318553003/diff/20001/src/IceCfgNode.h#newcod...
src/IceCfgNode.h:117: uint32_t LoopNestDepth = 0;      /// the loop nest depth
of this node
On 2015/09/01 22:17:37, stichnot wrote:
> Maybe the uint32_t should be SizeT?

Done.

https://codereview.chromium.org/1318553003/diff/20001/src/IceOperand.cpp
File src/IceOperand.cpp (right):

https://codereview.chromium.org/1318553003/diff/20001/src/IceOperand.cpp#newc...
src/IceOperand.cpp:163: constexpr uint32_t LogTypicalLoopTripCount = 3; // 2^3 =
8
On 2015/09/01 22:17:37, stichnot wrote:
> nit: "Typical" implies knowledge we don't have.  I think
> LogLoopTripCountEstimate would be better.

Done.

https://codereview.chromium.org/1318553003/diff/20001/src/IceOperand.cpp#newc...
src/IceOperand.cpp:164: uint32_t ThisUseWeight =
On 2015/09/01 22:17:37, stichnot wrote:
> Maybe SizeT instead of uint32_t?

Done.

https://codereview.chromium.org/1318553003/diff/20001/src/IceOperand.cpp#newc...
src/IceOperand.cpp:165: 1 << std::min(Node->getLoopNestDepth() *
LogTypicalLoopTripCount, 31u);
On 2015/09/01 22:17:37, stichnot wrote:
> No magic constants please. :)
> 
> CHAR_BIT * sizeof(ThisUseWeight) - 1

Done.

https://codereview.chromium.org/1318553003/diff/20001/src/IceOperand.cpp#newc...
src/IceOperand.cpp:408: return 1; // conservative answer
Is 1 the right number here? Why would a variable not be tracked? Does that mean
it isn't used?

https://codereview.chromium.org/1318553003/diff/20001/src/IceTargetLoweringX8...
File src/IceTargetLoweringX86BaseImpl.h (right):

https://codereview.chromium.org/1318553003/diff/20001/src/IceTargetLoweringX8...
src/IceTargetLoweringX86BaseImpl.h:332: // TODO: currently only used for
regalloc not expensive high level
On 2015/09/01 22:17:38, stichnot wrote:
> TODO(ascull,stichnot)

Done.

https://codereview.chromium.org/1318553003/diff/20001/src/IceTargetLoweringX8...
src/IceTargetLoweringX86BaseImpl.h:378: // liveness analysis. Loops must be
identified before livness to variable use
On 2015/09/01 22:17:38, stichnot wrote:
> On 2015/09/01 18:56:18, jvoung wrote:
> > "livness"
> > 
> > something sounds odd about "Loops must be identified before liveness to
> variable
> > use weights are correct"
> 
> I think you mean "so variable use"?

Done.

https://codereview.chromium.org/1318553003/diff/20001/tests_lit/llvm2ice_test...
File tests_lit/llvm2ice_tests/loop-nest-depth.ll (right):

https://codereview.chromium.org/1318553003/diff/20001/tests_lit/llvm2ice_test...
tests_lit/llvm2ice_tests/loop-nest-depth.ll:2: 
On 2015/09/01 18:56:18, jvoung wrote:
> Can you check that this works with "make -f Makefile.standalone MINIMAL=1
> check-lit"? I think it:
> 
> "REQUIRES: allow_dump"

Yep, MINIAL=1 fails but the require fixes things.

https://codereview.chromium.org/1318553003/diff/20001/tests_lit/llvm2ice_test...
tests_lit/llvm2ice_tests/loop-nest-depth.ll:6: 
On 2015/09/01 22:17:38, stichnot wrote:
> I'd like to see at least one test with loops and phi instructions (into and
out
> of the loop) and O2.  Perhaps simple_loop.ll is good enough.

Does the early exit satisfy this need?

All test are -O2 loop analysis only happen there.

https://codereview.chromium.org/1318553003/diff/20001/tests_lit/llvm2ice_test...
tests_lit/llvm2ice_tests/loop-nest-depth.ll:7: define void @test_single_loop(i1
%a) {
On 2015/09/01 18:56:18, jvoung wrote:
> Hmm, technically PNaCl does not allow i1 parameters, only i32 and larger
(i.e.,
> i64):
>
https://developer.chrome.com/native-client/reference/pnacl-bitcode-abi#scalar...
> (this is because most targets have 32-bit wide stack slots or parameter
> registers only, and you'd have to otherwise specify whether to sign extend or
> zero extend to fill it up).
> 
> So I worry that the bitcode reader could become stricter and break on this
test.
> 
> You could trunc i32 %a to i1 early in the function though.
> 
> Similar below.

Done.

https://codereview.chromium.org/1318553003/diff/20001/tests_lit/llvm2ice_test...
tests_lit/llvm2ice_tests/loop-nest-depth.ll:19: 
On 2015/09/01 18:56:18, jvoung wrote:
> Can you still CHECK-LABEL: test_single_loop
> 
> to help FileCheck partition the log?

Done.

https://codereview.chromium.org/1318553003/diff/20001/tests_lit/llvm2ice_test...
tests_lit/llvm2ice_tests/loop-nest-depth.ll:25: 
On 2015/09/01 18:56:18, jvoung wrote:
> Could add a "negative" test -- some non-loopy code with branches (like a
> diamond).
> 
> Also, what about something irreducible like example d in:
> https://en.wikipedia.org/wiki/Control_flow_graph#Definition
> 
> or something with multiple exits like c?

Done.

https://codereview.chromium.org/1318553003/diff/100001/src/IceOperand.cpp
File src/IceOperand.cpp (right):

https://codereview.chromium.org/1318553003/diff/100001/src/IceOperand.cpp#new...
src/IceOperand.cpp:167: << std::min(Node->getLoopNestDepth(), MaxLoopNestDepth)
* LogLoopTripCountEstimate;
Why does clang-format fail here? Should I just use a shorter name?

[Jim Stichnoth, 2015-09-03 21:35:09]

https://codereview.chromium.org/1318553003/diff/20001/src/IceOperand.cpp
File src/IceOperand.cpp (right):

https://codereview.chromium.org/1318553003/diff/20001/src/IceOperand.cpp#newc...
src/IceOperand.cpp:408: return 1; // conservative answer
On 2015/09/03 19:52:38, ascull wrote:
> Is 1 the right number here? Why would a variable not be tracked? Does that
mean
> it isn't used?

If the variable is not tracked, it usually means that the variable was created
after the VariablesMetadata was initialized.  VariablesMetadata tries to be
tolerant of that kind of situation.  1 seems like a perfectly reasonable default
in that case.

https://codereview.chromium.org/1318553003/diff/100001/src/IceCfgNode.cpp
File src/IceCfgNode.cpp (right):

https://codereview.chromium.org/1318553003/diff/100001/src/IceCfgNode.cpp#new...
src/IceCfgNode.cpp:1187: if (Func->isVerbose(IceV_Instructions) ||
Func->isVerbose(IceV_Loop))
I think it would be better to leave this line the way it was.

Instead, I would do something like this:

  if (Func->isVerbose(IceV_Instructions))
    Str << getName() << ":";
  // Dump the loop nest depth
  if (Func->isVerbose(IceV_Loop))
    Str << "    // LoopNestDepth = " << getLoopNestDepth();
  Str << "\n";

Then you'd have the label name and loop depth on the same line for easier
processing.  The test would have to be changed of course.

https://codereview.chromium.org/1318553003/diff/100001/src/IceDefs.h
File src/IceDefs.h (right):

https://codereview.chromium.org/1318553003/diff/100001/src/IceDefs.h#newcode295
src/IceDefs.h:295: inline bool add_overflow(uint32_t x, uint32_t y, uint32_t
*sum) {
Maybe this should go in IceUtils.h?  Also, document it.

https://codereview.chromium.org/1318553003/diff/100001/src/IceInst.h
File src/IceInst.h (right):

https://codereview.chromium.org/1318553003/diff/100001/src/IceInst.h#newcode24
src/IceInst.h:24: #include "IceOperand.h"
Why is this needed?

https://codereview.chromium.org/1318553003/diff/100001/src/IceLoopAnalyzer.cpp
File src/IceLoopAnalyzer.cpp (right):

https://codereview.chromium.org/1318553003/diff/100001/src/IceLoopAnalyzer.cp...
src/IceLoopAnalyzer.cpp:1: //===- subzero/src/IceLoopAnalyzer.cpp - Loop Anaysis
=====-----------------==//
Analysis --------===//

(misspelling plus dash/equals pattern)

https://codereview.chromium.org/1318553003/diff/100001/src/IceLoopAnalyzer.cp...
src/IceLoopAnalyzer.cpp:37: LoopAnalyzer::LoopAnalyzer(Cfg *Func) : Func(Func),
NumDeletedNodes(0) {
You can put "... NumDeletedNodes = 0;" in the member declarations.

https://codereview.chromium.org/1318553003/diff/100001/src/IceLoopAnalyzer.h
File src/IceLoopAnalyzer.h (right):

https://codereview.chromium.org/1318553003/diff/100001/src/IceLoopAnalyzer.h#...
src/IceLoopAnalyzer.h:21: /// Analyze the functions CFG for loops. The CFG must
not change during the
Drop the word "functions", or at least change to "function's".

https://codereview.chromium.org/1318553003/diff/100001/src/IceLoopAnalyzer.h#...
src/IceLoopAnalyzer.h:22: /// lifetine of this object.
lifetime

https://codereview.chromium.org/1318553003/diff/100001/src/IceLoopAnalyzer.h#...
src/IceLoopAnalyzer.h:51: explicit LoopNode(CfgNode *BB) : BB(BB),
Deleted(false) {}
Use "bool Deleted = false;" below instead of "Deleted(false)" here.

https://codereview.chromium.org/1318553003/diff/100001/src/IceLoopAnalyzer.h#...
src/IceLoopAnalyzer.h:80: NodeList::const_iterator Succ;
Make sure Succ/Index/LowLink/OnStack get initialized in the ctor.

https://codereview.chromium.org/1318553003/diff/100001/src/IceLoopAnalyzer.h#...
src/IceLoopAnalyzer.h:96: Cfg *Func;
Maybe Cfg *const Func;

https://codereview.chromium.org/1318553003/diff/100001/src/IceLoopAnalyzer.h#...
src/IceLoopAnalyzer.h:105: IndexT NextIndex;
Initialize NextIndex in the ctor

https://codereview.chromium.org/1318553003/diff/100001/src/IceOperand.cpp
File src/IceOperand.cpp (right):

https://codereview.chromium.org/1318553003/diff/100001/src/IceOperand.cpp#new...
src/IceOperand.cpp:167: << std::min(Node->getLoopNestDepth(), MaxLoopNestDepth)
* LogLoopTripCountEstimate;
On 2015/09/03 19:52:38, ascull wrote:
> Why does clang-format fail here? Should I just use a shorter name?

Maybe do the std::min() in a separate statement?

Maybe file a clang-format bug? :)

[ascull, 2015-09-03 22:47:13]

https://codereview.chromium.org/1318553003/diff/100001/src/IceCfgNode.cpp
File src/IceCfgNode.cpp (right):

https://codereview.chromium.org/1318553003/diff/100001/src/IceCfgNode.cpp#new...
src/IceCfgNode.cpp:1187: if (Func->isVerbose(IceV_Instructions) ||
Func->isVerbose(IceV_Loop))
On 2015/09/03 21:35:09, stichnot wrote:
> I think it would be better to leave this line the way it was.
> 
> Instead, I would do something like this:
> 
>   if (Func->isVerbose(IceV_Instructions))
>     Str << getName() << ":";
>   // Dump the loop nest depth
>   if (Func->isVerbose(IceV_Loop))
>     Str << "    // LoopNestDepth = " << getLoopNestDepth();
>   Str << "\n";
> 
> Then you'd have the label name and loop depth on the same line for easier
> processing.  The test would have to be changed of course.

Done.

https://codereview.chromium.org/1318553003/diff/100001/src/IceDefs.h
File src/IceDefs.h (right):

https://codereview.chromium.org/1318553003/diff/100001/src/IceDefs.h#newcode295
src/IceDefs.h:295: inline bool add_overflow(uint32_t x, uint32_t y, uint32_t
*sum) {
On 2015/09/03 21:35:09, stichnot wrote:
> Maybe this should go in IceUtils.h?  Also, document it.

Done.

https://codereview.chromium.org/1318553003/diff/100001/src/IceInst.h
File src/IceInst.h (right):

https://codereview.chromium.org/1318553003/diff/100001/src/IceInst.h#newcode24
src/IceInst.h:24: #include "IceOperand.h"
On 2015/09/03 21:35:09, stichnot wrote:
> Why is this needed?

Line 696 has a dyn_cast to Variable which requires the complete type. I came
across this when including IceDefs from LoopAnalyzer.

https://codereview.chromium.org/1318553003/diff/100001/src/IceLoopAnalyzer.cpp
File src/IceLoopAnalyzer.cpp (right):

https://codereview.chromium.org/1318553003/diff/100001/src/IceLoopAnalyzer.cp...
src/IceLoopAnalyzer.cpp:1: //===- subzero/src/IceLoopAnalyzer.cpp - Loop Anaysis
=====-----------------==//
On 2015/09/03 21:35:09, stichnot wrote:
> Analysis --------===//
> 
> (misspelling plus dash/equals pattern)

Done.

https://codereview.chromium.org/1318553003/diff/100001/src/IceLoopAnalyzer.cp...
src/IceLoopAnalyzer.cpp:37: LoopAnalyzer::LoopAnalyzer(Cfg *Func) : Func(Func),
NumDeletedNodes(0) {
On 2015/09/03 21:35:09, stichnot wrote:
> You can put "... NumDeletedNodes = 0;" in the member declarations.

Done.

https://codereview.chromium.org/1318553003/diff/100001/src/IceLoopAnalyzer.h
File src/IceLoopAnalyzer.h (right):

https://codereview.chromium.org/1318553003/diff/100001/src/IceLoopAnalyzer.h#...
src/IceLoopAnalyzer.h:21: /// Analyze the functions CFG for loops. The CFG must
not change during the
On 2015/09/03 21:35:09, stichnot wrote:
> Drop the word "functions", or at least change to "function's".

Done.

https://codereview.chromium.org/1318553003/diff/100001/src/IceLoopAnalyzer.h#...
src/IceLoopAnalyzer.h:22: /// lifetine of this object.
On 2015/09/03 21:35:09, stichnot wrote:
> lifetime

Done.

https://codereview.chromium.org/1318553003/diff/100001/src/IceLoopAnalyzer.h#...
src/IceLoopAnalyzer.h:51: explicit LoopNode(CfgNode *BB) : BB(BB),
Deleted(false) {}
On 2015/09/03 21:35:09, stichnot wrote:
> Use "bool Deleted = false;" below instead of "Deleted(false)" here.

Done.

https://codereview.chromium.org/1318553003/diff/100001/src/IceLoopAnalyzer.h#...
src/IceLoopAnalyzer.h:80: NodeList::const_iterator Succ;
On 2015/09/03 21:35:09, stichnot wrote:
> Make sure Succ/Index/LowLink/OnStack get initialized in the ctor.

Done.

https://codereview.chromium.org/1318553003/diff/100001/src/IceLoopAnalyzer.h#...
src/IceLoopAnalyzer.h:96: Cfg *Func;
On 2015/09/03 21:35:09, stichnot wrote:
> Maybe Cfg *const Func;

Done.

https://codereview.chromium.org/1318553003/diff/100001/src/IceLoopAnalyzer.h#...
src/IceLoopAnalyzer.h:105: IndexT NextIndex;
On 2015/09/03 21:35:09, stichnot wrote:
> Initialize NextIndex in the ctor

Done.

https://codereview.chromium.org/1318553003/diff/100001/src/IceOperand.cpp
File src/IceOperand.cpp (right):

https://codereview.chromium.org/1318553003/diff/100001/src/IceOperand.cpp#new...
src/IceOperand.cpp:167: << std::min(Node->getLoopNestDepth(), MaxLoopNestDepth)
* LogLoopTripCountEstimate;
On 2015/09/03 21:35:09, stichnot wrote:
> On 2015/09/03 19:52:38, ascull wrote:
> > Why does clang-format fail here? Should I just use a shorter name?
> 
> Maybe do the std::min() in a separate statement?
> 
> Maybe file a clang-format bug? :)

Done.

[Jim Stichnoth, 2015-09-03 23:23:30]

https://codereview.chromium.org/1318553003/diff/100001/src/IceInst.h
File src/IceInst.h (right):

https://codereview.chromium.org/1318553003/diff/100001/src/IceInst.h#newcode24
src/IceInst.h:24: #include "IceOperand.h"
On 2015/09/03 22:47:12, ascull wrote:
> On 2015/09/03 21:35:09, stichnot wrote:
> > Why is this needed?
> 
> Line 696 has a dyn_cast to Variable which requires the complete type. I came
> across this when including IceDefs from LoopAnalyzer.

Ah, thanks.  In that case, could you move the definition of getRmwBeacon into
IceInst.cpp, so that this include isn't needed?

https://codereview.chromium.org/1318553003/diff/100001/src/IceLoopAnalyzer.h
File src/IceLoopAnalyzer.h (right):

https://codereview.chromium.org/1318553003/diff/100001/src/IceLoopAnalyzer.h#...
src/IceLoopAnalyzer.h:80: NodeList::const_iterator Succ;
On 2015/09/03 22:47:13, ascull wrote:
> On 2015/09/03 21:35:09, stichnot wrote:
> > Make sure Succ/Index/LowLink/OnStack get initialized in the ctor.
> 
> Done.

I don't see this in the latest patchset.  To be clear, I think something like
this could be done:

explicit LoopNode(CfgNode *BB) : BB(BB), Succ(BB->getOutEdges().begin()) {}
...
IndexT Index = 0;
IndexT LowLink = 0;
bool OnStack = false;
bool Delete = false;

(maybe it's OK to ignore Succ initialization due to its complexity)

https://codereview.chromium.org/1318553003/diff/120001/src/IceCfgNode.cpp
File src/IceCfgNode.cpp (right):

https://codereview.chromium.org/1318553003/diff/120001/src/IceCfgNode.cpp#new...
src/IceCfgNode.cpp:1192: Str << "\n";
Whoops.  This "\n" should only be dumped if verbose is Instructions or Loop. 
Either add some more logic for that, or go back to your previous version.

EDIT: I have to say that the CHECK lines in the test look particularly icky with
the "//", so I would suggest just going back to your previous version.

https://codereview.chromium.org/1318553003/diff/120001/src/IceOperand.h
File src/IceOperand.h (right):

https://codereview.chromium.org/1318553003/diff/120001/src/IceOperand.h#newco...
src/IceOperand.h:331: if (Utils::add_overflow(Weight, Delta, &Weight) || Weight
== Inf)
This seems to have the interesting property that if Weight is Max, and Delta is
1, then the new Weight is actually Inf, whereas we probably want it to stay Max,
right?

[ascull, 2015-09-04 00:23:51]

https://codereview.chromium.org/1318553003/diff/100001/src/IceInst.h
File src/IceInst.h (right):

https://codereview.chromium.org/1318553003/diff/100001/src/IceInst.h#newcode24
src/IceInst.h:24: #include "IceOperand.h"
On 2015/09/03 23:23:30, stichnot wrote:
> On 2015/09/03 22:47:12, ascull wrote:
> > On 2015/09/03 21:35:09, stichnot wrote:
> > > Why is this needed?
> > 
> > Line 696 has a dyn_cast to Variable which requires the complete type. I came
> > across this when including IceDefs from LoopAnalyzer.
> 
> Ah, thanks.  In that case, could you move the definition of getRmwBeacon into
> IceInst.cpp, so that this include isn't needed?

Done.

https://codereview.chromium.org/1318553003/diff/100001/src/IceLoopAnalyzer.h
File src/IceLoopAnalyzer.h (right):

https://codereview.chromium.org/1318553003/diff/100001/src/IceLoopAnalyzer.h#...
src/IceLoopAnalyzer.h:80: NodeList::const_iterator Succ;
On 2015/09/03 23:23:30, stichnot wrote:
> On 2015/09/03 22:47:13, ascull wrote:
> > On 2015/09/03 21:35:09, stichnot wrote:
> > > Make sure Succ/Index/LowLink/OnStack get initialized in the ctor.
> > 
> > Done.
> 
> I don't see this in the latest patchset.  To be clear, I think something like
> this could be done:
> 
> explicit LoopNode(CfgNode *BB) : BB(BB), Succ(BB->getOutEdges().begin()) {}
> ...
> IndexT Index = 0;
> IndexT LowLink = 0;
> bool OnStack = false;
> bool Delete = false;
> 
> (maybe it's OK to ignore Succ initialization due to its complexity)

I call reset() in the constructor which initialized them. Is that ok or do they
need to be more strictly initialized?

https://codereview.chromium.org/1318553003/diff/120001/src/IceCfgNode.cpp
File src/IceCfgNode.cpp (right):

https://codereview.chromium.org/1318553003/diff/120001/src/IceCfgNode.cpp#new...
src/IceCfgNode.cpp:1192: Str << "\n";
On 2015/09/03 23:23:30, stichnot wrote:
> Whoops.  This "\n" should only be dumped if verbose is Instructions or Loop. 
> Either add some more logic for that, or go back to your previous version.
> 
> EDIT: I have to say that the CHECK lines in the test look particularly icky
with
> the "//", so I would suggest just going back to your previous version.

Done.

https://codereview.chromium.org/1318553003/diff/120001/src/IceOperand.h
File src/IceOperand.h (right):

https://codereview.chromium.org/1318553003/diff/120001/src/IceOperand.h#newco...
src/IceOperand.h:331: if (Utils::add_overflow(Weight, Delta, &Weight) || Weight
== Inf)
On 2015/09/03 23:23:30, stichnot wrote:
> This seems to have the interesting property that if Weight is Max, and Delta
is
> 1, then the new Weight is actually Inf, whereas we probably want it to stay
Max,
> right?

In that case Max + 1 = Inf which does not overflow but does == Inf so it will be
set to Max as it matches the second part of the logical or. maybe the confusion
is that add_overflow is actually doing the addition before comparing to Inf. I
believe this is defied behavior with the shortcut or?

[Jim Stichnoth, 2015-09-04 00:47:26]

lgtm

https://codereview.chromium.org/1318553003/diff/100001/src/IceLoopAnalyzer.h
File src/IceLoopAnalyzer.h (right):

https://codereview.chromium.org/1318553003/diff/100001/src/IceLoopAnalyzer.h#...
src/IceLoopAnalyzer.h:80: NodeList::const_iterator Succ;
On 2015/09/04 00:23:51, ascull wrote:
> On 2015/09/03 23:23:30, stichnot wrote:
> > On 2015/09/03 22:47:13, ascull wrote:
> > > On 2015/09/03 21:35:09, stichnot wrote:
> > > > Make sure Succ/Index/LowLink/OnStack get initialized in the ctor.
> > > 
> > > Done.
> > 
> > I don't see this in the latest patchset.  To be clear, I think something
like
> > this could be done:
> > 
> > explicit LoopNode(CfgNode *BB) : BB(BB), Succ(BB->getOutEdges().begin()) {}
> > ...
> > IndexT Index = 0;
> > IndexT LowLink = 0;
> > bool OnStack = false;
> > bool Delete = false;
> > 
> > (maybe it's OK to ignore Succ initialization due to its complexity)
> 
> I call reset() in the constructor which initialized them. Is that ok or do
they
> need to be more strictly initialized?

Ah, sorry, I missed the reset() call.

https://codereview.chromium.org/1318553003/diff/120001/src/IceOperand.h
File src/IceOperand.h (right):

https://codereview.chromium.org/1318553003/diff/120001/src/IceOperand.h#newco...
src/IceOperand.h:331: if (Utils::add_overflow(Weight, Delta, &Weight) || Weight
== Inf)
On 2015/09/04 00:23:51, ascull wrote:
> On 2015/09/03 23:23:30, stichnot wrote:
> > This seems to have the interesting property that if Weight is Max, and Delta
> is
> > 1, then the new Weight is actually Inf, whereas we probably want it to stay
> Max,
> > right?
> 
> In that case Max + 1 = Inf which does not overflow but does == Inf so it will
be
> set to Max as it matches the second part of the logical or. maybe the
confusion
> is that add_overflow is actually doing the addition before comparing to Inf. I
> believe this is defied behavior with the shortcut or?

OK, thanks, I'm convinced now.

[ascull, 2015-09-04 00:50:34]

Committed patchset #8 (id:140001) manually as
aa6c109366408d066c4ac9e22c8c0ded6d18092f (presubmit successful).