Skip to content

Tracking issue for FastISel #26600

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom
Closed
1 of 5 tasks
pcwalton opened this issue Jun 26, 2015 · 12 comments
Closed
1 of 5 tasks

Tracking issue for FastISel #26600

pcwalton opened this issue Jun 26, 2015 · 12 comments
Labels
A-codegen Area: Code generation A-LLVM Area: Code generation parts specific to LLVM. Both correctness bugs and optimization-related issues. I-compiletime Issue: Problems and improvements with respect to compile times.

Comments

@pcwalton
Copy link
Contributor

We are currently falling off FastISel to the optimized SelectionDAG instruction selector in pretty much every function, hurting our codegen time in debug builds. You can verify this by running llc -O0 -fast-isel -fast-isel-abort. We have the following issues:

  • FastISel does not support the invoke instruction. Proposed solution: Add this support to LLVM.
  • FastISel does not support the switch instruction. Proposed solution: Add this support to LLVM.
  • FastISel does not support comparisons on i1. Proposed solution: Add this support to LLVM.
  • FastISel does not support the llvm.assume intrinsic. Proposed solution: Ignore that intrinsic in LLVM.
  • FastISel does not allow first-class aggregates to be used, but we use first-class aggregates when loading and storing slices (e.g. store { i8*, i32 } %1, %2). Proposed solution: Stop doing this in trans.
@pcwalton pcwalton added A-LLVM Area: Code generation parts specific to LLVM. Both correctness bugs and optimization-related issues. A-codegen Area: Code generation I-compiletime Issue: Problems and improvements with respect to compile times. labels Jun 26, 2015
@dotdash
Copy link
Contributor

dotdash commented Jun 27, 2015

Did #26595 fix the FCA problem?

@emberian
Copy link
Member

We should add a test for this in-tree as well. A good strategy is probably going to be adding those LLVM arguments with the -Z flag and building run-pass tests with it...

@emberian
Copy link
Member

@pcwalton Are you working on an upstream patch or is that free to be taken?

@dotdash dotdash mentioned this issue Jul 2, 2015
Merged
dotdash added a commit to dotdash/rust that referenced this issue Jul 2, 2015
@dotdash
Directly construct lvalue datums for function arguments
a04784f 
The current split between create_datums_for_fn_args,
copy_args_to_allocas and store_arg involves a detour via rvalue datums
which cause additional work in form of insertvalue/extractvalue pairs
for fat pointer arguments, and an extra alloca and memcpy for tupled
args in rust-call functions.

By merging those three functions into just one that actually covers the
whole process of creating the final argument datums, we can skip all
that. Also, this allows to easily merge in the handling of rust-call
functions, allowing to make create_datum_for_fn_args_under_call_abi
obsolete.

cc rust-lang#26600 -- The insertvalue instructions kicked us off of fast-isel.
bors added a commit that referenced this issue Jul 2, 2015
@bors
Auto merge of #26738 - dotdash:trans_args, r=luqmana

Verified

This commit was signed with the committer’s verified signature.
lunny Lunny Xiao
GPG key ID: C3B7C91B632F738A
Verified
Learn about vigilant mode
546ab50 
The current split between create_datums_for_fn_args, copy_args_to_allocas and
store_arg involves a detour via rvalue datums which cause additional work in
form of insertvalue/extractvalue pairs for fat pointer arguments, and an extra
alloca and memcpy for tupled args in rust-call functions.

By merging those three functions into just one that actually covers the whole
process of creating the final argument datums, we can skip all that.  Also,
this allows to easily merge in the handling of rust-call functions, allowing to
make create_datum_for_fn_args_under_call_abi obsolete.

cc #26600 -- The insertvalue instructions kicked us off of fast-isel.
bors added a commit that referenced this issue Jul 2, 2015
@bors
Auto merge of #26738 - dotdash:trans_args, r=luqmana

Verified

This commit was created on GitHub.com and signed with GitHub’s verified signature. The key has expired.
GPG key ID: 4AEE18F83AFDEB23
Expired
Verified
Learn about vigilant mode
b4abed6 
The current split between create_datums_for_fn_args, copy_args_to_allocas and
store_arg involves a detour via rvalue datums which cause additional work in
form of insertvalue/extractvalue pairs for fat pointer arguments, and an extra
alloca and memcpy for tupled args in rust-call functions.

By merging those three functions into just one that actually covers the whole
process of creating the final argument datums, we can skip all that.  Also,
this allows to easily merge in the handling of rust-call functions, allowing to
make create_datum_for_fn_args_under_call_abi obsolete.

cc #26600 -- The insertvalue instructions kicked us off of fast-isel.
@jonas-schievink
Copy link
Contributor

Triage:

fn main() {
    Vec::<u8>::new();
}

(this creates an absurd amount of code)
With rustc --emit=llvm-ir -Zno-landing-pads test.rs

llc -O0 -fast-isel -fast-isel-abort 1 test.ll gives, using the llc shipped with the current Rust master:

FastISel missed terminator:   switch i1 %29, label %match_else [
    i1 true, label %match_case
    i1 false, label %match_case3
  ]
FastISel missed terminator:   ret { i8*, i64 } %20
FastISel missed terminator:   ret { i8*, i64 } %7
FastISel miss:   %24 = icmp eq i1 %23, true
LLVM ERROR: FastISel didn't select the entire block

And with the llc of LLVM 3.7.1:

FastISel missed terminator:   switch i1 %29, label %match_else [
    i1 true, label %match_case
    i1 false, label %match_case3
  ]
FastISel missed call:   call void @llvm.assume(i1 %25)
FastISel missed terminator:   ret { i8*, i64 } %20
FastISel missed terminator:   ret { i8*, i64 } %7
FastISel missed call:   call void @llvm.assume(i1 %28)
FastISel missed call:   call void @llvm.assume(i1 %20)
FastISel miss:   %24 = icmp eq i1 %23, true
LLVM ERROR: FastISel didn't select the entire block

(on x86_64 Arch Linux)

Rust's own llc is better probably because of rust-lang/llvm@e37f45f, but I'm not sure why the icmp still isn't selected. @pcwalton any thoughts?

The switch i1 is just silly, it could be replaced by a br i1, but that's #4353

@arielb1
Copy link
Contributor

arielb1 commented Feb 15, 2016

Yes trans is sure to load and store every value quite a bit of times.

@alexcrichton alexcrichton mentioned this issue Feb 29, 2016
Merged
@JohanEngelen JohanEngelen mentioned this issue Apr 28, 2016
Closed
@Mark-Simulacrum Mark-Simulacrum added the C-tracking-issue Category: An issue tracking the progress of sth. like the implementation of an RFC label Jul 22, 2017
@nox
Copy link
Contributor

nox commented Mar 30, 2018

Cc @rust-lang/wg-compiler-performance.

@nox
Copy link
Contributor

nox commented Apr 2, 2018

Note that FastISel is apparently intended to be replaced by GlobalISel in the future.

@hanna-kruppe
Copy link
Contributor

But also note that it will be many years until GlobalISel is production quality for all the architectures we care about.

@ishitatsuyuki
Copy link
Contributor

I think the switch part is now handled in at least LLVM 5+, can anybody verify?

@steveklabnik
Copy link
Member

Triage: i just tried @jonas-schievink 's example on godbolt's llvm-trunk, and got

LLVM ERROR: FastISel missed:   store { i64, i64 } %2, { i64, i64 }* %_5, align 8 (in function: _ZN49_$LT$alloc..raw_vec..RawVec$LT$T$C$$u20$A$GT$$GT$14dealloc_buffer17h67e71990b9ebed9cE)

Compiler returned: 1

@workingjubilee
Copy link
Member

Reproduction for me was somewhat easier with a crate, wielding the example code given by Jonas:

fn main() {
    Vec::<u8>::new();
}

and the command

cargo rustc -- -Cremark=all -Cdebuginfo=2 -Cpanic=abort

though I hope I got it right, as it emits somewhat more... enthusiastic diagnostics:

FastISel Didn't Lower ${YES_EVEN_THAT} 
note: optimization missed for sdagisel at <unknown file>:0:0: FastISel didn't lower all arguments: i8* (i64, i64)* (in function: __rust_alloc)
note: optimization missed for sdagisel at <unknown file>:0:0: FastISel missed call (in function: __rust_alloc)
note: optimization missed for sdagisel at <unknown file>:0:0: FastISel didn't lower all arguments: void (i8*, i64, i64)* (in function: __rust_dealloc)
note: optimization missed for sdagisel at <unknown file>:0:0: FastISel missed call (in function: __rust_dealloc)
note: optimization missed for sdagisel at <unknown file>:0:0: FastISel didn't lower all arguments: i8* (i8*, i64, i64, i64)* (in function: __rust_realloc)
note: optimization missed for sdagisel at <unknown file>:0:0: FastISel missed call (in function: __rust_realloc)
note: optimization missed for sdagisel at <unknown file>:0:0: FastISel didn't lower all arguments: i8* (i64, i64)* (in function: __rust_alloc_zeroed)
note: optimization missed for sdagisel at <unknown file>:0:0: FastISel missed call (in function: __rust_alloc_zeroed)
note: optimization missed for sdagisel at <unknown file>:0:0: FastISel didn't lower all arguments: void (i64, i64)* (in function: __rust_alloc_error_handler)
note: optimization missed for sdagisel at <unknown file>:0:0: FastISel missed call (in function: __rust_alloc_error_handler)
note: optimization missed for sdagisel at /rustc/6c2dd251bbff03c7a3092d43fb5b637eca0810e3\library\alloc\src\raw_vec.rs:255:0: FastISel didn't lower all arguments: void (%"std::option::Option<(std::ptr::NonNull<u8>, std::alloc::Layout)>"*, { i8*, i64 }*)*
note: optimization missed for sdagisel at ${PATH}\example\src\main.rs:1:0: FastISel didn't lower all arguments: void ()*
note: optimization missed for sdagisel at <unknown file>:0:0: FastISel didn't lower all arguments: i32 (i32, i8**)* (in function: main)
note: optimization missed for sdagisel at /rustc/6c2dd251bbff03c7a3092d43fb5b637eca0810e3\library\alloc\src\raw_vec.rs:238:0: FastISel didn't lower all arguments: i8* ({ i8*, i64 }*)*
note: optimization missed for sdagisel at /rustc/6c2dd251bbff03c7a3092d43fb5b637eca0810e3\library\core\src\ops\function.rs:227:0: FastISel didn't lower all arguments: i32 (i64**)*
note: optimization missed for sdagisel at /rustc/6c2dd251bbff03c7a3092d43fb5b637eca0810e3\library\core\src\ops\function.rs:227:0: FastISel didn't lower all arguments: i32 (i64*)*
note: optimization missed for sdagisel at /rustc/6c2dd251bbff03c7a3092d43fb5b637eca0810e3\library\std\src\process.rs:1996:0: FastISel didn't lower all arguments: i32 ()*
note: optimization missed for sdagisel at /rustc/6c2dd251bbff03c7a3092d43fb5b637eca0810e3\library\core\src\ops\function.rs:227:0: FastISel didn't lower all arguments: void (void ()*)*
note: optimization missed for sdagisel at /rustc/6c2dd251bbff03c7a3092d43fb5b637eca0810e3\library\core\src\ptr\mod.rs:192:0: FastISel didn't lower all arguments: void (%"std::vec::Vec<u8>"*)*
note: optimization missed for sdagisel at /rustc/6c2dd251bbff03c7a3092d43fb5b637eca0810e3\library\std\src\process.rs:2030:0: FastISel didn't lower all arguments: i32 (i32)*
note: optimization missed for sdagisel at /rustc/6c2dd251bbff03c7a3092d43fb5b637eca0810e3\library\core\src\ptr\mod.rs:192:0: FastISel didn't lower all arguments: void ({ i8*, i64 }*)*
note: optimization missed for sdagisel at /rustc/6c2dd251bbff03c7a3092d43fb5b637eca0810e3\library\core\src\ptr\mod.rs:192:0: FastISel didn't lower all arguments: void (i64**)*
note: optimization missed for sdagisel at /rustc/6c2dd251bbff03c7a3092d43fb5b637eca0810e3\library\alloc\src\alloc.rs:103:0: FastISel didn't lower all arguments: void (i8*, i64, i64)*
note: optimization missed for sdagisel at /rustc/6c2dd251bbff03c7a3092d43fb5b637eca0810e3\library\alloc\src\vec\mod.rs:2711:0: FastISel didn't lower all arguments: void (%"std::vec::Vec<u8>"*)*
note: optimization missed for sdagisel at /rustc/6c2dd251bbff03c7a3092d43fb5b637eca0810e3\library\alloc\src\raw_vec.rs:519:0: FastISel didn't lower all arguments: void ({ i8*, i64 }*)*
note: optimization missed for sdagisel at /rustc/6c2dd251bbff03c7a3092d43fb5b637eca0810e3\library\alloc\src\alloc.rs:235:0: FastISel didn't lower all arguments: void (%"std::alloc::Global"*, i8*, i64, i64)*
note: optimization missed for sdagisel at /rustc/6c2dd251bbff03c7a3092d43fb5b637eca0810e3\library\std\src\sys\windows\process.rs:438:0: FastISel didn't lower all arguments: i32 (i32*)*
note: optimization missed for sdagisel at /rustc/6c2dd251bbff03c7a3092d43fb5b637eca0810e3\library\core\src\ptr\unique.rs:87:0: FastISel didn't lower all arguments: i8* (i8*)*
note: optimization missed for sdagisel at /rustc/6c2dd251bbff03c7a3092d43fb5b637eca0810e3\library\core\src\ptr\unique.rs:135:0: FastISel didn't lower all arguments: i8* (i8*)*
note: optimization missed for sdagisel at /rustc/6c2dd251bbff03c7a3092d43fb5b637eca0810e3\library\core\src\ptr\unique.rs:105:0: FastISel didn't lower all arguments: i8* (i8*)*
note: optimization missed for sdagisel at /rustc/6c2dd251bbff03c7a3092d43fb5b637eca0810e3\library\core\src\hint.rs:159:0: FastISel didn't lower all arguments: void ()*
note: optimization missed for sdagisel at /rustc/6c2dd251bbff03c7a3092d43fb5b637eca0810e3\library\core\src\hint.rs:170:0: FastISel missed call
note: optimization missed for sdagisel at /rustc/6c2dd251bbff03c7a3092d43fb5b637eca0810e3\library\core\src\convert\mod.rs:537:0: FastISel didn't lower all arguments: i8* (i8*)*
note: optimization missed for sdagisel at /rustc/6c2dd251bbff03c7a3092d43fb5b637eca0810e3\library\core\src\ptr\mut_ptr.rs:433:0: FastISel didn't lower all arguments: i1 (i8*, i8*)*
note: optimization missed for sdagisel at /rustc/6c2dd251bbff03c7a3092d43fb5b637eca0810e3\library\core\src\ptr\mut_ptr.rs:36:0: FastISel didn't lower all arguments: i1 (i8*)*
note: optimization missed for sdagisel at /rustc/6c2dd251bbff03c7a3092d43fb5b637eca0810e3\library\core\src\num\nonzero.rs:53:0: FastISel didn't lower all arguments: i64 (i64)*
note: optimization missed for sdagisel at /rustc/6c2dd251bbff03c7a3092d43fb5b637eca0810e3\library\core\src\num\nonzero.rs:75:0: FastISel didn't lower all arguments: i64 (i64)*
note: optimization missed for sdagisel at /rustc/6c2dd251bbff03c7a3092d43fb5b637eca0810e3\library\std\src\rt.rs:43:0: FastISel didn't lower all arguments: i64 (void ()*, i64, i8**)*
note: optimization missed for sdagisel at /rustc/6c2dd251bbff03c7a3092d43fb5b637eca0810e3\library\std\src\rt.rs:49:0: FastISel didn't lower all arguments: i32 (i64**)*
note: optimization missed for sdagisel at /rustc/6c2dd251bbff03c7a3092d43fb5b637eca0810e3\library\std\src\sys_common\backtrace.rs:121:0: FastISel didn't lower all arguments: void (void ()*)*
note: optimization missed for sdagisel at /rustc/6c2dd251bbff03c7a3092d43fb5b637eca0810e3\library\core\src\ptr\non_null.rs:596:0: FastISel didn't lower all arguments: i8* (i8*)*
note: optimization missed for sdagisel at /rustc/6c2dd251bbff03c7a3092d43fb5b637eca0810e3\library\core\src\ptr\non_null.rs:161:0: FastISel didn't lower all arguments: i8* (i8*)*
note: optimization missed for sdagisel at /rustc/6c2dd251bbff03c7a3092d43fb5b637eca0810e3\library\core\src\ptr\non_null.rs:211:0: FastISel didn't lower all arguments: i8* (i8*)*
note: optimization missed for sdagisel at /rustc/6c2dd251bbff03c7a3092d43fb5b637eca0810e3\library\core\src\ptr\mod.rs:293:0: FastISel didn't lower all arguments: { [0 x i8]*, i64 } (i8*, i64)*
note: optimization missed for sdagisel at /rustc/6c2dd251bbff03c7a3092d43fb5b637eca0810e3\library\core\src\ptr\mod.rs:295:0: FastISel missed terminator
note: optimization missed for sdagisel at /rustc/6c2dd251bbff03c7a3092d43fb5b637eca0810e3\library\core\src\ptr\metadata.rs:127:0: FastISel didn't lower all arguments: { [0 x i8]*, i64 } ({}*, i64)*
note: optimization missed for sdagisel at /rustc/6c2dd251bbff03c7a3092d43fb5b637eca0810e3\library\core\src\ptr\metadata.rs:135:0: FastISel missed terminator
note: optimization missed for sdagisel at /rustc/6c2dd251bbff03c7a3092d43fb5b637eca0810e3\library\core\src\alloc\layout.rs:98:0: FastISel didn't lower all arguments: { i64, i64 } (i64, i64)*
note: optimization missed for sdagisel at /rustc/6c2dd251bbff03c7a3092d43fb5b637eca0810e3\library\core\src\alloc\layout.rs:101:0: FastISel missed terminator
note: optimization missed for sdagisel at /rustc/6c2dd251bbff03c7a3092d43fb5b637eca0810e3\library\core\src\alloc\layout.rs:107:0: FastISel didn't lower all arguments: i64 ({ i64, i64 }*)*
note: optimization missed for sdagisel at /rustc/6c2dd251bbff03c7a3092d43fb5b637eca0810e3\library\alloc\src\vec\mod.rs:419:0: FastISel didn't lower all arguments: void (%"std::vec::Vec<u8>"*)*
note: optimization missed for sdagisel at /rustc/6c2dd251bbff03c7a3092d43fb5b637eca0810e3\library\core\src\alloc\layout.rs:115:0: FastISel didn't lower all arguments: i64 ({ i64, i64 }*)*
note: optimization missed for sdagisel at /rustc/6c2dd251bbff03c7a3092d43fb5b637eca0810e3\library\alloc\src\vec\mod.rs:1167:0: FastISel didn't lower all arguments: i8* (%"std::vec::Vec<u8>"*)*

Currently, GlobalISel is within 1.5 the speed of FastISel according to https://llvm.org/docs/GlobalISel/index.html and they have some ambitions for getting it within 1.1 or 1.2 in time, so it seems likely that GlobalISel will close this issue before FastISel grows the relevant support.

@pnkfelix
Copy link
Member

pnkfelix commented Mar 4, 2022 •
edited
Loading

Discussed at today's T-compiler backlog bonanza.

Based on investigations in previous comments, it seems like we're unlikely to invest effort here and we're unlikely to see FastISel actually be suitable in the short term.

@rust-lang/wg-llvm , especially @nagisa and @nikic , I'm closing this, but feel free to reopen if you think it is worth having it open.

@rustbot label -C-tracking-issue

@pnkfelix pnkfelix closed this as completed Mar 4, 2022
@rustbot rustbot removed the C-tracking-issue Category: An issue tracking the progress of sth. like the implementation of an RFC label Mar 4, 2022
@workingjubilee workingjubilee mentioned this issue Jul 6, 2022
Closed
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
A-codegen Area: Code generation A-LLVM Area: Code generation parts specific to LLVM. Both correctness bugs and optimization-related issues. I-compiletime Issue: Problems and improvements with respect to compile times.
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests