Sort allocas, compute frame pointer in Cfg pass

Sort allocas, compute frame pointer in Cfg pass

Split allocas in the entry block into two categories.  The first has alignment <= stack alignment and constant size.  The second violates one or both of those conditions.  Sort both of these lists in descending alignment order and emit.  Also, compute the need for a frame pointer during the pass.

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

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

[sehr, 2015-11-06 18:18:27]

Description was changed from

==========
Fix overly-conservative ebp detection

Any instruction that is not a variable or highly aligned alloca does not
interfere with known stack offsets.

BUG=
==========

to

==========
Sort allocas, compute frame pointer in Cfg pass

Split allocas in the entry block into two categories.  The first has alignment
<= stack alignment and constant size.  The second violates one or both of those
conditions.  Sort both of these lists in descending alignment order and emit. 
Also, compute the need for a frame pointer during the pass.

BUG=
==========

[sehr, 2015-11-06 18:18:28]

sehr@chromium.org changed reviewers:
+ jpp@chromium.org, kschimpf@chromium.org, stichnot@chromium.org

[sehr, 2015-11-06 18:19:39]

Please review this first.  I've decided to refactor the big alloca cl into this
first.  Then I will fuse the allocas separately.  Finally, I will add the
rematerialization.

[John, 2015-11-06 18:23:00]

lgtm

[Jim Stichnoth, 2015-11-06 18:44:11]

otherwise lgtm

https://codereview.chromium.org/1414343010/diff/40001/src/IceCfg.cpp
File src/IceCfg.cpp (right):

https://codereview.chromium.org/1414343010/diff/40001/src/IceCfg.cpp#newcode454
src/IceCfg.cpp:454: void Cfg::sortAllocas(std::vector<Inst *> &Allocas, InstList
&Insts,
Use CfgVector instead of std::vector here and below.

https://codereview.chromium.org/1414343010/diff/40001/src/IceCfg.cpp#newcode456
src/IceCfg.cpp:456: if (Allocas.size() == 0)
.empty()

[Jim Stichnoth, 2015-11-06 18:45:27]

https://codereview.chromium.org/1414343010/diff/40001/src/IceCfg.cpp
File src/IceCfg.cpp (right):

https://codereview.chromium.org/1414343010/diff/40001/src/IceCfg.cpp#newcode458
src/IceCfg.cpp:458: // Sort by decreasing alignment.
This is so that they get prepended in order of increasing alignment?  Because
the stack grows downward?  Maybe add that to the comment.

[sehr, 2015-11-06 19:01:15]

Thanks for the reviews.  PTAL.

https://codereview.chromium.org/1414343010/diff/40001/src/IceCfg.cpp
File src/IceCfg.cpp (right):

https://codereview.chromium.org/1414343010/diff/40001/src/IceCfg.cpp#newcode454
src/IceCfg.cpp:454: void Cfg::sortAllocas(std::vector<Inst *> &Allocas, InstList
&Insts,
On 2015/11/06 18:44:11, stichnot wrote:
> Use CfgVector instead of std::vector here and below.

Done.

https://codereview.chromium.org/1414343010/diff/40001/src/IceCfg.cpp#newcode456
src/IceCfg.cpp:456: if (Allocas.size() == 0)
On 2015/11/06 18:44:11, stichnot wrote:
> .empty()

Done.

https://codereview.chromium.org/1414343010/diff/40001/src/IceCfg.cpp#newcode458
src/IceCfg.cpp:458: // Sort by decreasing alignment.
On 2015/11/06 18:45:27, stichnot wrote:
> This is so that they get prepended in order of increasing alignment?  Because
> the stack grows downward?  Maybe add that to the comment.

It's sort of arbitrary in the general sense here, since the alloca expansion
still emits an alignment every time an alloca is seen that has larger than stack
alignment.  In the next CL, when I fuse allocas into one, sorting them in
decreasing alignment order allows me to pack the allocas more tightly.

[sehr, 2015-11-06 19:25:45]

Committed patchset #5 (id:80001) manually as
e39d0ca2c6a0cbc6e68b6d4323f0f8cfb1914840 (presubmit successful).