Subzero: Loop Invariant Code Motion

Loop Invariant Code Motion

Implemented behind the new -licm flag.
Hoists invariant arithmetic instructions from loop bodies to pre-headers.
Does not trigger for loops where headers have two incoming edges from
outside the loop.
Also enables multi block address optimization, because most of the
instructions hoisted are address calculations coming from gep.

Does not touch memory operations.
This algorithm does not seem to work well for load-hoisting.

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=f47d520c1a91bb029d73a5a5f7c0e416ed763f23

[manasijm, 2016-07-08 20:06:19]

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

[John, 2016-07-08 21:04:46]

lgtm

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

https://codereview.chromium.org/2138443002/diff/1/src/IceCfg.cpp#newcode643
src/IceCfg.cpp:643: void Cfg::loopInvariantCodeMotion() {
please create a helper function named "findLoopInvariantInstructions" (or
something similar) and move the first half of this code over.

https://codereview.chromium.org/2138443002/diff/1/src/IceCfg.cpp#newcode669
src/IceCfg.cpp:669: CfgUnorderedSet<Inst *> InvariantInsts;
Given that this is a set, this will probably not help much, but how about
hoisting this declaration to the top of this function, and then invoke "clear()"
on them here?

https://codereview.chromium.org/2138443002/diff/1/src/IceCfg.cpp#newcode670
src/IceCfg.cpp:670: CfgUnorderedSet<Variable *> InvariantVars;
please create a helper function named "findLoopInvariantInstructions" (or
something similar) and move the next loops to that function.

https://codereview.chromium.org/2138443002/diff/1/src/IceCfg.cpp#newcode675
src/IceCfg.cpp:675: do {
I tend to prefer using worklist-based iteration instead of this solution. Your
call.

https://codereview.chromium.org/2138443002/diff/1/src/IceCfg.cpp#newcode723
src/IceCfg.cpp:723: auto &LastInst = Insts.back();
Why the special handling of Insts.back?

[manasijm, 2016-07-08 21:09:31]

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

https://codereview.chromium.org/2138443002/diff/1/src/IceCfg.cpp#newcode669
src/IceCfg.cpp:669: CfgUnorderedSet<Inst *> InvariantInsts;
On 2016/07/08 21:04:46, John wrote:
> Given that this is a set, this will probably not help much, but how about
> hoisting this declaration to the top of this function, and then invoke
"clear()"
> on them here?

This is why I was advocating a stack allocator :)

https://codereview.chromium.org/2138443002/diff/1/src/IceCfg.cpp#newcode670
src/IceCfg.cpp:670: CfgUnorderedSet<Variable *> InvariantVars;
On 2016/07/08 21:04:46, John wrote:
> please create a helper function named "findLoopInvariantInstructions" (or
> something similar) and move the next loops to that function.

Will do.

https://codereview.chromium.org/2138443002/diff/1/src/IceCfg.cpp#newcode723
src/IceCfg.cpp:723: auto &LastInst = Insts.back();
On 2016/07/08 21:04:46, John wrote:
> Why the special handling of Insts.back?

It is a control flow instruction, can not insert other stuff after it.

[Jim Stichnoth, 2016-07-12 10:51:52]

lgtm

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

https://codereview.chromium.org/2138443002/diff/20001/src/IceCfg.cpp#newcode678
src/IceCfg.cpp:678: Ice::CfgVector<Inst *>
add extra blank line

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

https://codereview.chromium.org/2138443002/diff/20001/src/IceLoopAnalyzer.h#n...
src/IceLoopAnalyzer.h:39: // is bounded linear. ncbray suggests another
algorithm whichis  linear in
undo this

[manasijm, 2016-07-12 23:59:20]

Description was changed from

==========
Loop Invariant Code Motion

Implemented behind the new -licm flag.
Hoists invariant arithmetic instructions from loop bodies to pre-headers.
Does not trigger for loops where headers have two incoming edges from
outside the loop.
Also enables multi block address optimization, because most of the
instructions hoisted are address calculations coming from gep.

Does not touch memory operations.
This algorithm does not seem to work well for load-hoisting.

BUG=none
==========

to

==========
Loop Invariant Code Motion

Implemented behind the new -licm flag.
Hoists invariant arithmetic instructions from loop bodies to pre-headers.
Does not trigger for loops where headers have two incoming edges from
outside the loop.
Also enables multi block address optimization, because most of the
instructions hoisted are address calculations coming from gep.

Does not touch memory operations.
This algorithm does not seem to work well for load-hoisting.

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-12 23:59:22]

Committed patchset #3 (id:40001) manually as
f47d520c1a91bb029d73a5a5f7c0e416ed763f23 (presubmit successful).