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

[swift-ci]

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:

• [SR-7703] Creating an array with 10.000 elements is slow with optimization. #50243

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]

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]

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]

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]

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