Subzero: Align spill locations to natural alignment.

Subzero: Align spill locations to natural alignment.

This requires sorting the spilled variables based on alignment and
introducing additional padding around the spill location areas.

These changes allow vector instructions to accept memory operands.

Old stack frame layout:  New stack frame layout:
+---------------------+  +---------------------+
| return address      |  | return address      |
+---------------------+  +---------------------+
| preserved registers |  | preserved registers |
+---------------------+  +---------------------+
| global spill area   |  | padding             |
+---------------------+  +---------------------+
| local spill area    |  | global spill area   |
+---------------------+  +---------------------+
| padding             |  | padding             |
+---------------------+  +---------------------+
| local variables     |  | local spill area    |
+---------------------+  +---------------------+
                         | padding             |
                         +---------------------+
                         | local variables     |
                         +---------------------+

BUG=none
R=jvoung@chromium.org, stichnot@chromium.org

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

[wala, 2014-08-13 23:22:01]

This removes the ugly LEGAL_HACKs from the lowering code. Yay!!

[Jim Stichnoth, 2014-08-13 23:59:35]

https://codereview.chromium.org/465413003/diff/20001/src/IceTargetLoweringX86...
File src/IceTargetLoweringX8632.cpp (right):

https://codereview.chromium.org/465413003/diff/20001/src/IceTargetLoweringX86...
src/IceTargetLoweringX8632.cpp:530: typedef std::map<uint32_t, VarList>
BucketMap;
Use a list<> or vector<> instead of map<> ?

https://codereview.chromium.org/465413003/diff/20001/src/IceTargetLoweringX86...
src/IceTargetLoweringX8632.cpp:630: uint32_t LocalsSlotsAlignmentBytes = 0;
At this point, the stack frame layout is starting to get complex enough that it
would be nice to have a beautiful ascii art diagram of the frame like in this CL
description, labeled with the local variables that contain the size of each
section.

https://codereview.chromium.org/465413003/diff/20001/src/IceTargetLoweringX86...
src/IceTargetLoweringX8632.cpp:795: else {
Probably best to have braces around both clauses or neither clause.

https://codereview.chromium.org/465413003/diff/20001/tests_lit/llvm2ice_tests...
File tests_lit/llvm2ice_tests/align-spill-locations.ll (right):

https://codereview.chromium.org/465413003/diff/20001/tests_lit/llvm2ice_tests...
tests_lit/llvm2ice_tests/align-spill-locations.ll:6: ; RUN:               |
llvm-mc -arch=x86 -x86-asm-syntax=intel -filetype=obj
Change the -arch lines per https://codereview.chromium.org/467103004/ .

https://codereview.chromium.org/465413003/diff/20001/tests_lit/llvm2ice_tests...
tests_lit/llvm2ice_tests/align-spill-locations.ll:14: define <4 x i32>
@align_global_vector(i32 %arg) {
Document the meaning of global versus local, otherwise the reader may assume
LLVM globals.

[jvoung (off chromium), 2014-08-14 00:48:49]

yay for removing LEGAL_HACKs!

https://codereview.chromium.org/465413003/diff/20001/src/IceTargetLoweringX86...
File src/IceTargetLoweringX8632.cpp (right):

https://codereview.chromium.org/465413003/diff/20001/src/IceTargetLoweringX86...
src/IceTargetLoweringX8632.cpp:725: LocalsSizeBytes += NewGlobalsSize -
GlobalsSize;
Isn't this difference always going to be zero?

Do you want to move the assignment of GlobalsSize = NewGlobalsSize to below this
+= ?

[Jim Stichnoth, 2014-08-14 16:48:29]

https://codereview.chromium.org/465413003/diff/20001/src/IceTargetLoweringX86...
File src/IceTargetLoweringX8632.cpp (right):

https://codereview.chromium.org/465413003/diff/20001/src/IceTargetLoweringX86...
src/IceTargetLoweringX8632.cpp:530: typedef std::map<uint32_t, VarList>
BucketMap;
On 2014/08/13 23:59:34, stichnot wrote:
> Use a list<> or vector<> instead of map<> ?

Never mind this comment, I misread the code.

[wala, 2014-08-14 17:31:24]

https://codereview.chromium.org/465413003/diff/20001/src/IceTargetLoweringX86...
File src/IceTargetLoweringX8632.cpp (right):

https://codereview.chromium.org/465413003/diff/20001/src/IceTargetLoweringX86...
src/IceTargetLoweringX8632.cpp:530: typedef std::map<uint32_t, VarList>
BucketMap;
On 2014/08/13 23:59:34, stichnot wrote:
> Use a list<> or vector<> instead of map<> ?

There are only 4 possible buckets (corresponding to the type sizes). I ended up
using an array.

https://codereview.chromium.org/465413003/diff/20001/src/IceTargetLoweringX86...
src/IceTargetLoweringX8632.cpp:630: uint32_t LocalsSlotsAlignmentBytes = 0;
On 2014/08/13 23:59:34, stichnot wrote:
> At this point, the stack frame layout is starting to get complex enough that
it
> would be nice to have a beautiful ascii art diagram of the frame like in this
CL
> description, labeled with the local variables that contain the size of each
> section.

Done.

https://codereview.chromium.org/465413003/diff/20001/src/IceTargetLoweringX86...
src/IceTargetLoweringX8632.cpp:725: LocalsSizeBytes += NewGlobalsSize -
GlobalsSize;
On 2014/08/14 00:48:49, jvoung wrote:
> Isn't this difference always going to be zero?
> 
> Do you want to move the assignment of GlobalsSize = NewGlobalsSize to below
this
> += ?

Ouch, I'm surprised all the tests still passed.

Done: The logic has been changed so that the padding size is properly added to
LocalsSizeBytes. Also, the variables have been renamed for clarity.

I've also added a unit test to exercise this case.

https://codereview.chromium.org/465413003/diff/20001/src/IceTargetLoweringX86...
src/IceTargetLoweringX8632.cpp:770: if (Var->getWeight() == RegWeight::Zero &&
Var->getRegisterOverlap()) {
Since I've separated out the list of variables linked to a variable with a spill
slot from the list of spilled variables, I don't think this statement is
necessary, so I've removed it.

https://codereview.chromium.org/465413003/diff/20001/src/IceTargetLoweringX86...
src/IceTargetLoweringX8632.cpp:795: else {
On 2014/08/13 23:59:34, stichnot wrote:
> Probably best to have braces around both clauses or neither clause.

Done.

https://codereview.chromium.org/465413003/diff/20001/tests_lit/llvm2ice_tests...
File tests_lit/llvm2ice_tests/align-spill-locations.ll (right):

https://codereview.chromium.org/465413003/diff/20001/tests_lit/llvm2ice_tests...
tests_lit/llvm2ice_tests/align-spill-locations.ll:6: ; RUN:               |
llvm-mc -arch=x86 -x86-asm-syntax=intel -filetype=obj
On 2014/08/13 23:59:34, stichnot wrote:
> Change the -arch lines per https://codereview.chromium.org/467103004/ .

These aren't really necessary, so I've removed them instead.

https://codereview.chromium.org/465413003/diff/20001/tests_lit/llvm2ice_tests...
tests_lit/llvm2ice_tests/align-spill-locations.ll:14: define <4 x i32>
@align_global_vector(i32 %arg) {
On 2014/08/13 23:59:34, stichnot wrote:
> Document the meaning of global versus local, otherwise the reader may assume
> LLVM globals.

Done.

[wala, 2014-08-14 17:51:59]

https://codereview.chromium.org/465413003/diff/20001/src/IceTargetLoweringX86...
File src/IceTargetLoweringX8632.cpp (right):

https://codereview.chromium.org/465413003/diff/20001/src/IceTargetLoweringX86...
src/IceTargetLoweringX8632.cpp:530: typedef std::map<uint32_t, VarList>
BucketMap;
On 2014/08/14 17:31:24, wala wrote:
> On 2014/08/13 23:59:34, stichnot wrote:
> > Use a list<> or vector<> instead of map<> ?
> 
> There are only 4 possible buckets (corresponding to the type sizes). I ended
up
> using an array.

Actually, there are 3 usable buckets (4 bytes, 8 bytes, 16 bytes).

[Jim Stichnoth, 2014-08-14 18:21:19]

https://codereview.chromium.org/465413003/diff/40001/src/IceTargetLoweringX86...
File src/IceTargetLoweringX8632.cpp (right):

https://codereview.chromium.org/465413003/diff/40001/src/IceTargetLoweringX86...
src/IceTargetLoweringX8632.cpp:27: #include <strings.h>
Use MathExtras.h and llvm::findFirstSet(), since JF says it's awesomer.

https://codereview.chromium.org/465413003/diff/120001/src/IceTargetLoweringX8...
File src/IceTargetLoweringX8632.cpp (right):

https://codereview.chromium.org/465413003/diff/120001/src/IceTargetLoweringX8...
src/IceTargetLoweringX8632.cpp:535: void TargetX8632::sortByAlignment(VarList
&Dest, const VarList &Source) const {
Does this need to be part of TargetX8632, or can it be static / in an anonymous
namespace?

[wala, 2014-08-14 18:24:11]

https://codereview.chromium.org/465413003/diff/120001/src/IceTargetLoweringX8...
File src/IceTargetLoweringX8632.cpp (right):

https://codereview.chromium.org/465413003/diff/120001/src/IceTargetLoweringX8...
src/IceTargetLoweringX8632.cpp:535: void TargetX8632::sortByAlignment(VarList
&Dest, const VarList &Source) const {
On 2014/08/14 18:21:19, stichnot wrote:
> Does this need to be part of TargetX8632, or can it be static / in an
anonymous
> namespace?

It needs access to TargetLoweringX8632::typeWidthInBytesOnStack().

[jvoung (off chromium), 2014-08-14 18:40:59]

https://codereview.chromium.org/465413003/diff/120001/src/IceTargetLoweringX8...
File src/IceTargetLoweringX8632.cpp (right):

https://codereview.chromium.org/465413003/diff/120001/src/IceTargetLoweringX8...
src/IceTargetLoweringX8632.cpp:629: //  * LocalsSizeBytes:        areas 3 - 7
There's a couple of notions of Locals here, local-var-spill and allocas (called
local variables in the above diagram?).

Since "LocalsSizeBytes" refers to 3 thru 7, would it make more sense to call it
"SpillAreaSizeBytes", or something like that, so that it's not confused with
area 8? Also, an expression like "LocalsSizeBytes += GlobalsSize" looks a bit
funny.

[wala, 2014-08-14 19:47:01]

https://codereview.chromium.org/465413003/diff/120001/src/IceTargetLoweringX8...
File src/IceTargetLoweringX8632.cpp (right):

https://codereview.chromium.org/465413003/diff/120001/src/IceTargetLoweringX8...
src/IceTargetLoweringX8632.cpp:629: //  * LocalsSizeBytes:        areas 3 - 7
On 2014/08/14 18:40:59, jvoung wrote:
> There's a couple of notions of Locals here, local-var-spill and allocas
(called
> local variables in the above diagram?).
> 
> Since "LocalsSizeBytes" refers to 3 thru 7, would it make more sense to call
it
> "SpillAreaSizeBytes", or something like that, so that it's not confused with
> area 8? Also, an expression like "LocalsSizeBytes += GlobalsSize" looks a bit
> funny.

Done.

[jvoung (off chromium), 2014-08-14 20:36:57]

lgtm

[Jim Stichnoth, 2014-08-14 21:00:31]

Also LGTM

[wala, 2014-08-14 21:24:18]

Committed patchset #7 manually as d4799f4 (presubmit successful).