Skip to content
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

[SR-9235] RedundantLoadElimination is slow with a large static array. #51723

Closed
swift-ci opened this issue Nov 13, 2018 · 4 comments
Closed

[SR-9235] RedundantLoadElimination is slow with a large static array. #51723

swift-ci opened this issue Nov 13, 2018 · 4 comments
Labels
bug A deviation from expected or documented behavior. Also: expected but undesirable behavior. compiler The Swift compiler in itself duplicate Resolution: Duplicates another issue expressions Feature: expressions literals Feature → expressions: Literals such as an integer or string literal optimized only Flag: An issue whose reproduction requires optimized compilation performance SILOptimizer Area → compiler: SIL optimization passes

Comments

@swift-ci
Copy link
Collaborator

swift-ci commented Nov 13, 2018 •
edited by AnthonyLatsis

Previous ID SR-9235
Radar None
Original Reporter andreasw (JIRA User)
Type Bug
Status Resolved
Resolution Duplicate

Attachment: Download

Environment

Makefile

Additional Detail from JIRA
Votes 0
Component/s Compiler
Labels Bug, Performance
Assignee None
Priority Medium

md5: 68468fc66829b4d2a218088ed7f66a10

duplicates:

Issue Description:

A large array with 5.000 or 10.000 elements massively slows down compilation.

Here is a Makefile to generate such an array and a stack trace.

+ 60,00% 0,01% swift swift [.] (anonymous namespace)::RedundantLoadElimination::run ◆
+ 51,24% 4,69% swift swift [.] (anonymous namespace)::BlockState::processStoreInst ▒
+ 41,50% 26,75% swift swift [.] llvm::DenseMapBase<llvm::SmallDenseMap<swift::LSLocation, unsigned int, 32u, llvm::DenseMapInfo<swift::L▒
+ 32,74% 3,33% swift swift [.] swift::LSLocation::isMayAliasLSLocation ▒
+ 29,62% 0,15% swift swift [.] swift::LSLocation::enumerateLSLocations ▒
+ 29,49% 0,08% swift swift [.] swift::LSLocation::enumerateLSLocation ▒
+ 19,92% 0,00% swift swift [.] swift::SILPassManager::runFunctionPasses ▒
+ 19,83% 0,01% swift swift [.] swift::SILPassManager::runPassOnFunction ▒
+ 19,12% 5,04% swift swift [.] swift::AliasAnalysis::alias ▒
+ 14,57% 14,52% swift swift [.] swift::ProjectionPath::computeSubSeqRelation ▒
+ 10,29% 10,29% swift swift [.] swift::ProjectionPath::hasNonEmptySymmetricDifference ▒
+ 9,06% 0,00% swift swift [.] swift::SILPassManager::execute ▒
+ 7,26% 7,26% swift swift [.] swift::ValueEnumerator<swift::ValueBase*, unsigned long>::getIndex ▒
+ 6,83% 6,82% swift swift [.] llvm::DenseMapBase<llvm::DenseMap<(anonymous namespace)::AliasKeyTy, swift::AliasAnalysis::AliasResult, ▒
+ 5,97% 0,02% swift swift [.] llvm::DenseMapBase<llvm::SmallDenseMap<swift::LSLocation, unsigned int, 32u, llvm::DenseMapInfo<swift::L▒
+ 5,96% 0,00% swift swift [.] llvm::SmallDenseMap<swift::LSLocation, unsigned int, 32u, llvm::DenseMapInfo<swift::LSLocation>, llvm::d
@belkadan
Copy link
Contributor

Please don't assign issues to people unless you've already been talking with them; just mention them in the text instead. (In particular, Xin no longer works on Swift.)

cc @eeckstein

@swift-ci
Copy link
Collaborator Author

Comment by Andreas Wendleder (JIRA)

I'm sorry. I didn't know the rules here. I did a "git shortlog" on the files related to RLE and chose the person with the most commits. I hope it's ok now.

@swift-ci
Copy link
Collaborator Author

Comment by Andreas Wendleder (JIRA)

It seems RLE is exposing quadratic complexity. I have timings and a diagram here:

https://docs.google.com/spreadsheets/d/16VakcOYvcwZbmPRLxO_1HcLUwCx0xEVT5mXWYsYnQjY/edit#gid=0

The second column is for SR-9223, a bug in the inliner, but the diagram shows that there is something wrong with RLE, too.

I hope to revisit the timings once SR-9223 is fixed.

@atrick
Copy link
Member

atrick commented Nov 17, 2018

Ideally the pass would be redesigned, but in the meantime we should probably place a limit on the analysis.

@swift-ci swift-ci transferred this issue from apple/swift-issues Apr 25, 2022
@gonsolo gonsolo mentioned this issue Oct 4, 2022
Closed
@AnthonyLatsis AnthonyLatsis added SILOptimizer Area → compiler: SIL optimization passes duplicate Resolution: Duplicates another issue literals Feature → expressions: Literals such as an integer or string literal expressions Feature: expressions optimized only Flag: An issue whose reproduction requires optimized compilation labels Apr 26, 2023
This issue was closed.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
bug A deviation from expected or documented behavior. Also: expected but undesirable behavior. compiler The Swift compiler in itself duplicate Resolution: Duplicates another issue expressions Feature: expressions literals Feature → expressions: Literals such as an integer or string literal optimized only Flag: An issue whose reproduction requires optimized compilation performance SILOptimizer Area → compiler: SIL optimization passes
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
4 participants
@belkadan @atrick @swift-ci @AnthonyLatsis