Refactor type memory layouts and ABIs, to be more general and easier to optimize. by eddyb · Pull Request #45225 · rust-lang/rust

eddyb · 2017-10-12T02:34:06Z

To combat combinatorial explosion, type layouts are now described through 3 orthogonal properties:

Variants describes the plurality of sum types (where applicable)
- Single is for one inhabited/active variant, including all C structs and unions
- Tagged has its variants discriminated by an integer tag, including C enums
- NicheFilling uses otherwise-invalid values ("niches") for all but one of its inhabited variants
FieldPlacement describes the number and memory offsets of fields (if any)
- Union has all its fields at offset 0
- Array has offsets that are a multiple of its stride; guarantees all fields have one type
- Arbitrary records all the field offsets, which can be out-of-order
Abi describes how values of the type should be passed around, including for FFI
- Uninhabited corresponds to no values, associated with unreachable control-flow
- Scalar is ABI-identical to its only integer/floating-point/pointer "scalar component"
- ScalarPair has two "scalar components", but only applies to the Rust ABI
- Vector is for SIMD vectors, typically #[repr(simd)] structs in Rust
- Aggregate has arbitrary contents, including all non-transparent C structs and unions

Size optimizations implemented so far:

ignoring uninhabited variants (i.e. containing uninhabited fields), e.g.:
- Option<!> is 0 bytes
- Result<T, !> has the same size as T
using arbitrary niches, not just 0, to represent a data-less variant, e.g.:
- Option<bool>, Option<Option<bool>>, Option<Ordering> are all 1 byte
- Option<char> is 4 bytes
using a range of niches to represent multiple data-less variants, e.g.:
- enum E { A(bool), B, C, D } is 1 byte

Code generation now takes advantage of Scalar and ScalarPair to, in more cases, pass around scalar components as immediates instead of indirectly, through pointers into temporary memory, while avoiding LLVM's "first-class aggregates", and there's more untapped potential here.

Closes #44426, fixes #5977, fixes #14540, fixes #43278.

rust-highfive · 2017-10-12T02:34:18Z

r? @nikomatsakis

(rust_highfive has picked a reviewer for you, use r? to override)

eddyb · 2017-10-12T02:37:52Z

Started a crater run (we'll run cargobomb later, but that takes longer).

Gankra · 2017-10-12T02:48:00Z

holy shit

scottmcm · 2017-10-12T07:06:10Z

Wow! I think this might fix #43278 too.

arielb1 · 2017-10-12T10:20:07Z

src/librustc_trans/mir/lvalue.rs

Why is this always 1? Because you do a pointercast instead of a gep in the offset 0 case?

Yes, and the assert ensures it.

arielb1 · 2017-10-12T10:55:04Z

src/test/run-pass/issue-30276.rs

Why are you removing this test?

This is one of those things that don't trigger a typeck error but is totally broken, and I didn't want to deal with it.

What does "totally broken" mean in this context?

Something hid the ICE and #30276 was closed, but that was accidental. This is more or less a bug in WF-checking of function arguments in signatures, which @nikomatsakis somewhat insisted on keeping around, which allows fn(Unsized) to even exist (it shouldn't, for now).

arielb1 · 2017-10-12T10:55:52Z

src/test/codegen/packed.rs

Is the case this test was intended to check unreachable?

Now, yeah, ScalarPair only works by having the placement of the second scalar at an ABI-aligned offset, so it's incompatible with packing.

arielb1 · 2017-10-12T11:14:54Z

src/librustc/ty/layout.rs

Why do "general" enums use FieldPlacement::Union for the discriminant only and "niche" enums use FieldPlacement::Arbitrary?

Because a tag is always at offset 0 whereas a niche can be at some offset - we could have a variant of FieldPlacement that's just one Size to avoid the Vec but that's about it.

But why we can't use FieldPlacement::Arbitrary for both of them? "Normal" structs with one field don't suddenly use FieldPlacement::Union because they can.

I mean, FieldPlacement::Arbitrary is a bit of a waste, and I considered using FieldPlacement::Union for normal structs too, but then I have checks for Union in some places which would conflict with that now. I think you're right and I should make the change here.

EDIT: done.

EDIT2: That's funny, not using FieldPlacement::Union results in some missed optimizations (codegen/{alloc-optimisation,vec-optimizes-away}). I'll try to see what I can do about it.

EDIT3: None of the tricks I've tried work, I'll just leave it like this to avoid pessimizing tagged enums for now.

Maybe add a comment to that effect?

eddyb · 2017-10-12T23:03:39Z

I've just moved Uninhabited from Variants to Abi - that way, we can still compute field types for uninhabited types, but also signal the fact that there's no valid values anyway.

eddyb · 2017-10-12T23:54:27Z

@scottmcm Your original example from #43278 compiles to a single ret i32 %0 with this PR.

mrhota · 2017-10-13T07:51:26Z

@eddyb also would seem to fix #5977

any relevance to #14540? #6791? And am I right in thinking this work puts us on a path for doing some of the optimizations here rust-lang/rfcs#1230?

For travelers from the future, also see the older, far less ambitious PRs #31215 and #36237.

bors · 2017-10-13T09:01:16Z

☔ The latest upstream changes (presumably #45031) made this pull request unmergeable. Please resolve the merge conflicts.

eddyb · 2017-10-13T14:47:08Z

@mrhota Are you sure you meant #6791? That issue was closed more than three years ago.

The problem with #31215 and #36237 was that they only added code where this PR is a net negative.

This PR implements most of rust-lang/rfcs#1230, the description there is confused in places (i.e. it's a list of special cases, but several of them happen to be the exact same optimization, just scattered).
The cases I couldn't do here:

Option<Option<(&T, &U)>> requires us to initialize the second &U with a non-zero value for the inner Option, which we don't do right now (and could be expensive in general)
enum E { A(&T / Enum / etc., A...), B(B...), C(C...) } (where A... takes up at least as much space as each of B... and C...) requires trickier search logic, and would be hard/impossible to integrate with the current rustc_trans::mir::constant, we'd have to wait for miri to experiment with it
enum F { A(T, A), B(T, B) } as (T, enum G { A(A), B(B) }) where we already are able to optimize G - this includes enum Foo { A(&u8, &u8), B(&u8) } and many others - requires effectively a 2D layout process (although, just like the previous case, it's tricky and there may be many valid approaches) and will likely need a bunch more caching, around niches probably

EDIT: for an updated view on these hard cases, see rust-lang/rfcs#1230 (comment).

My approach with this PR has been to avoid doing anything that would pessimize codegen, and one example of this is that enum X { A(bool), B, C } and enum Y { A, B, C(bool) } use (invalid for bool) values 2 and 3 for the nullary variants, but enum Z { A, B(bool), C } uses 2 and 4, wasting 3, which (if you were to transmute it) matches B, to avoid a more runtime-expensive value remapping when the discriminant value is needed (e.g. for every match).

eddyb · 2017-10-13T16:27:56Z

I can't reproduce the Travis failure locally, even after commenting out most of my config.toml 😞

eddyb · 2017-10-13T17:28:33Z

@alexcrichton @Mark-Simulacrum I hope you don't mind that I just pushed a temporary commit to build on Travis without LLVM 3.7, to check if it's some old LLVM bug getting triggered.

eddyb · 2017-10-13T19:18:08Z

Confirmed successful build with newer (4.0?) LLVM. I'll try to reproduce locally.

eddyb · 2017-10-13T23:05:52Z

@alexcrichton @Mark-Simulacrum May I suggest outputting a signal number by default?
Currently, all I see (for example, in Travis CI) is:

error: Could not compile `quote`.

But if I turn verbose mode on, there's an extra (manually wrapped for your convenience):

Caused by:
  process didn't exit successfully: `
/home/eddy/Projects/rust-2/build/bootstrap/debug/rustc --crate-name quote
/home/eddy/.cargo/registry/src/github.com-1ecc6299db9ec823/quote-0.3.15/src/lib.rs
--crate-type lib --emit=dep-info,link -C opt-level=2 -C metadata=396e074f31421a34
-C extra-filename=-396e074f31421a34
--out-dir /home/eddy/Projects/rust-2/build/x86_64-unknown-linux-gnu/stage2-tools/release/deps
-L dependency=/home/eddy/Projects/rust-2/build/x86_64-unknown-linux-gnu/stage2-tools/release/deps
--cap-lints allow` (signal: 11, SIGSEGV: invalid memory reference)

Printing just "rustc exited with signal: 11, SIGSEGV: invalid memory reference" by default would be really great, although I'd understand if it's too much of an edge case to bother with.

rust-highfive assigned nikomatsakis Oct 12, 2017

eddyb mentioned this pull request Oct 12, 2017

Move layout & ABI code into s/librustc_back/librustc_target. #45226

Closed

eddyb force-pushed the trans-abi branch from 2b0e0b2 to e27cba8 Compare October 12, 2017 09:36

arielb1 reviewed Oct 12, 2017

View reviewed changes

eddyb force-pushed the trans-abi branch from e27cba8 to a3f7156 Compare October 12, 2017 10:35

arielb1 reviewed Oct 12, 2017

View reviewed changes

eddyb force-pushed the trans-abi branch 2 times, most recently from c0e7215 to 08eb7c7 Compare October 12, 2017 23:01

eddyb force-pushed the trans-abi branch 2 times, most recently from a5b5722 to d595119 Compare October 12, 2017 23:51

eddyb force-pushed the trans-abi branch from d595119 to 436e8aa Compare October 13, 2017 03:18

eddyb force-pushed the trans-abi branch from 436e8aa to 3504ac6 Compare October 13, 2017 14:48

kennytm added the S-waiting-on-author Status: This is awaiting some action (such as code changes or more information) from the author. label Oct 13, 2017

eddyb force-pushed the trans-abi branch 2 times, most recently from 4c4d081 to 5d92b1a Compare October 13, 2017 17:40

RReverser mentioned this pull request Dec 22, 2017

Tracking issue for NonZero/Unique/Shared stabilization #27730

Closed

Lokathor mentioned this pull request Dec 27, 2017

repr(Rust) page doesn't reflect the latest data layout optimizations rust-lang/nomicon#51

Closed

kennytm mentioned this pull request Dec 28, 2017

Collapse trailing padding #17027

Closed

daboross mentioned this pull request Dec 28, 2017

Segfault on Xorg on rustc 1.23.0-beta.2 rust-windowing/glutin#973

Closed

This was referenced Jan 10, 2018

Only mark unions as uninhabited if all of their fields are uninhabited #46859

Merged

rustc: ensure optimized enums have a properly aligned size. #46808

Merged

powerpc: ICE when taking and returning C struct containing u64 #47278

Closed

dtolnay mentioned this pull request Jan 19, 2018

[!; 0] incorrectly considered uninhabited #47563

Closed

eddyb mentioned this pull request Jan 22, 2018

Fix GDB pretty-printers for compressed enums #47617

Closed

niklasf mentioned this pull request Jan 23, 2018

debug performance regression between nightly-2017-11-20 and nightly-2017-11-21 niklasf/shakmaty#11

Closed

dtolnay mentioned this pull request Jan 27, 2018

LLVM error with trait objects #47638

Closed

glandium mentioned this pull request Mar 23, 2018

rustc fails to remove dead code in exactly one instance of multiple similar code #48627

Closed

alexcrichton mentioned this pull request Apr 12, 2018

core: Inline From<AllocErr> for CollectionAllocErr #49850

Merged

dtolnay mentioned this pull request Apr 15, 2018

Incorrect niche filling if enum contains both i32 min and i32 max variants #49973

Closed

This was referenced May 17, 2018

Enums with only one variant and without #[repr(_)] have size 0 in 1.27 beta #50830

Closed

Don't ignore alignment anymore in ArgType::make_indirect #50299

Closed

Emerentius mentioned this pull request Jun 4, 2018

Extend null-pointer enum optimization to nested enums #23228

Closed

tromey mentioned this pull request Jun 7, 2018

Add DWARF for discriminated unions rust-lang/llvm#118

Merged

emilyalbini mentioned this pull request Jul 5, 2018

ICE when using an object-safe trait with methods marked as extern #51907

Closed

pnkfelix mentioned this pull request Sep 4, 2018

Using a match statement on a field of an enum results in an internal compiler error #53728

Closed

tromey mentioned this pull request Sep 8, 2018

Fix DWARF generation for enums #54004

Merged

eddyb mentioned this pull request Sep 23, 2018

Missed optimization: references from pointers aren't treated as noalias #38941

Open

varkor mentioned this pull request Apr 23, 2019

Make str a struct str([u8]) rust-lang/rfcs#2692

Open

eddyb mentioned this pull request Apr 30, 2019

Multi-variant layouts for generators #59897

Merged

eddyb mentioned this pull request Jun 27, 2019

Soundness hole in pattern matching on enums with an uninhabited variant #61696

Closed

erikdesjardins mentioned this pull request Jul 2, 2020

Ignore ZST offsets when deciding whether to use Scalar/ScalarPair layout #73453

Merged

nagisa mentioned this pull request Jan 8, 2021

Set attrs.pointee_align when constructing function ABI #80822

Closed

cuviper mentioned this pull request Jul 28, 2022

Compiling ndarray: alignment mismatch between ABI and layout #99836

Closed

ickk mentioned this pull request Oct 19, 2022

Turn the Visibility struct into an enum bevyengine/bevy#6271

Closed

RalfJung mentioned this pull request Aug 27, 2023

fix some issues around ZST handling #115277

Merged

Uh oh!

Conversation

eddyb commented Oct 12, 2017 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

rust-highfive commented Oct 12, 2017

Uh oh!

eddyb commented Oct 12, 2017

Uh oh!

Gankra commented Oct 12, 2017

Uh oh!

scottmcm commented Oct 12, 2017

Uh oh!

arielb1 Oct 12, 2017 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

eddyb Oct 12, 2017 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

arielb1 Oct 12, 2017 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

eddyb Oct 12, 2017 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

eddyb commented Oct 12, 2017

Uh oh!

eddyb commented Oct 12, 2017

Uh oh!

mrhota commented Oct 13, 2017

Uh oh!

bors commented Oct 13, 2017

Uh oh!

eddyb commented Oct 13, 2017 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

eddyb commented Oct 13, 2017

Uh oh!

eddyb commented Oct 13, 2017

Uh oh!

eddyb commented Oct 13, 2017

Uh oh!

eddyb commented Oct 13, 2017 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

20 participants

eddyb commented Oct 12, 2017 •

edited

Loading

arielb1 Oct 12, 2017 •

edited

Loading

eddyb Oct 12, 2017 •

edited

Loading

arielb1 Oct 12, 2017 •

edited

Loading

eddyb Oct 12, 2017 •

edited

Loading

eddyb commented Oct 13, 2017 •

edited

Loading

eddyb commented Oct 13, 2017 •

edited

Loading