Repository: rust
Issue: Optimize codegen scheduling
Labels: A-codegen,C-tracking-issue

Updated tracking issue for [#82685][OriginalIssue]

## Overview

The original issue provides a great introduction to and overview of the problem, as well as a proposed solution to it; but there are relevant issues and detail missing from the issue that I would like to add, and I would like to bring it up to date and 
organize it so the issue can be addressed more cohesively to form a long-term solution.

I'd like to thank @tgnottingham for all the posts and work he did on this, as they gave me a lot of insight into the overall issue and it's resolution. I'd also like to mention @wesleywiser for providing an apt [comparison][WesleyWiserQuote] 
to the [multiway partitioning problem][MultiWayPart]. The general solution lies in minimizing the "make span" of the problem (CGU compilation finish time), which can be achieved by minimizing the largest "sum" (CGU).

However, before we can attempt to minimize the largest CGU we must address all of the issues that are currently plagueing CGU size in general. Monomorphization partitioning is the obvious candidate for consideration; and it's possible the issues regarding [inlining][InlineImplementation] and [drops][DropsInLLVM-IR] take place there. These issues may also be [related][DropsAlwaysInlined]. I am assuming that a lot of programs [use match statements to initialize struct fields][LLVMBloatStructInit]; so the code bloat there is something that should be looked into as well.

More importantly, there is the fact that while CGU scheduling is correctly organized by size, the metric used to gauge CGU size [is supposedly not correct][CGUSizeMetric]; which suggests that the first order of business is making it so. I plan on tackling this first, so any advice that can be offered in regards to that would be appreciated. Immensely.

## Thoughts

While it is possible that small improvements can be made over time to yield performance wins, these tweaks may not be be cohesive or consider other necessary parts of the compiler, which is why to address this effectively we need to organize all relevant information into one place, and create a roadmap that resolves these issues and gets us to the high-level general solution of simply minimizing the largest CGU. In general, we need collaboration.


## Metrics

We need a way to track the metrics we are looking to optimize. In general, we need to track different size and time
metrics for individual CGU's from when they are initially partitioned, to when they are ready to be linked. We also need metrics for codegen in general, so we can see how size/time for individual CGU's affects codegen overall. Right now the
only metric I have thought of for tracking this is total time from partitioning to linking. We also need to be able to determine if a CGU is large because it started out large, or if it is large because it has been merged with other CGU's.

Metric Types:
  - CGU: metrics for individual CGU's
  - CG: metrics for codegen in general

| Type | Metric | Description | 
|------|-------| -------------|
|  CGU |  size   |   Total LLVM instructions            |
| CGU | compilation time |  Total time to translate LLVM-IR to a compiled CGU |
| CGU | optimization time|  Total time to completely optimize a CGU |
| CGU | total time | compilation time + optimization time |
| CG | total time | Total time from partitioning to linking (when all compiled CGU's are ready to be linked, not when linking has finished) |

## Road to Optimization

This is not permanent; I am hoping others offer suggestions and improvements.

- [ ] Add per-CGU metrics to perf.r-l.o
    - Map CGU's to a CGU ID
    - Correct size metric; track CGU size
    - Add support for determining if CGU's are large because they were
       merged or if they began that way
    - Should the metric simply be the number of LLVM instructions in a CGU?
- [ ] Address inlining implementation
    - Going to need a lot of help here
- [ ] Address Drops always being inlined
    - And here
- [ ] Address LLVM bloat when using match struct-field initialization
    - And here
- [ ] Implement algorithm to identify largest CGU and minimize it
    - Should the amount of CGU's minimized be determined by the amount of cores?

# References

[Original Issue][OriginalIssue]
[CGU Size Metric][CGUSizeMetric]
[CGU Organization][CGUOrganization]
[CGU Compile Time][CGUCompileTime]
[LLVM Bloat Match Statement][LLVMBloatStructInit]
[Inline Implementation][InlineImplementation]
[Drops Always Inlined][DropsAlwaysInlined]
[Drops In LLVM IR][DropsInLLVM-IR]
[Suboptimal Codegen Parallelism][SuboptimalCodegenParallelism]
[Wesley Wiser Comparison][WesleyWiserQuote]
[Multiway Partitioning][MultiWayPart]

[OriginalIssue]:https://github.com/rust-lang/rust/issues/82685
[CGUSizeMetric]:https://github.com/rust-lang/rust/issues/69382
[CGUOrganization]:https://github.com/rust-lang/rust/pull/81736
[CGUCompileTime]:https://github.com/rust-lang/rust/pull/81538
[LLVMBloatStructInit]:https://github.com/rust-lang/rust/issues/68822
[InlineImplementation]:https://github.com/rust-lang/rust/issues/14527
[DropsAlwaysInlined]:https://github.com/rust-lang/rust/issues/64140
[DropsInLLVM-IR]:https://github.com/rust-lang/rust/issues/38827
[SuboptimalCodegenParallelism]:https://github.com/rust-lang/rust/issues/64913
[WesleyWiserQuote]:https://github.com/rust-lang/rust/issues/82685#issuecomment-788964038
[MultiWayPart]:https://en.wikipedia.org/wiki/Multiway_number_partitioning