This is an archive of the discontinued LLVM Phabricator instance.

[Transforms][GlobalSRA] huge array causes long compilation time and huge memory usage.
ClosedPublic

Authored by avl on Dec 30 2019, 3:46 AM.

Details

Summary

For artificial cases (huge array, few usages), Global SRA optimization creates
a lot of redundant data. It creates an instance of GlobalVariable for each array
element. For huge array, that means huge compilation time and huge memory usage.
Following example compiles for 10 minutes and requires 40GB of memory.

namespace {

char LargeBuffer[64 * 1024 * 1024];

}

int main ( void ) {

LargeBuffer[0] = 0;

printf("\n ");

return LargeBuffer[0] == 0;

}

The fix is to avoid Global SRA for large arrays.

Diff Detail

Event Timeline

avl created this revision.Dec 30 2019, 3:46 AM
Herald added a project: Restricted Project. · View Herald TranscriptDec 30 2019, 3:46 AM
Herald added a subscriber: hiraditya. · View Herald Transcript

Unit tests: fail. 61141 tests passed, 2 failed and 728 were skipped.

failed: LLVM.CodeGen/Mips/GlobalISel/legalizer/bitreverse.mir
failed: LLVM.CodeGen/Mips/GlobalISel/llvm-ir/bitreverse.ll

clang-tidy: pass.

clang-format: pass.

Build artifacts: diff.json, clang-tidy.txt, clang-format.patch, CMakeCache.txt, console-log.txt, test-results.xml

lkail added a subscriber: lkail.Dec 30 2019, 4:13 AM
avl added a comment.Dec 30 2019, 6:16 AM

above two failures do not relate to my fix. Patch which introduced them is already reverted : https://reviews.llvm.org/rG32cc14100e802fddd9f88e7a862250ce3108a583

lebedev.ri added inline comments.
llvm/lib/Transforms/IPO/GlobalOpt.cpp
512–513

It looks like this makes bailout more strict, therefore it likely regresses something else?

avl marked an inline comment as done.Dec 30 2019, 6:49 AM
avl added inline comments.
llvm/lib/Transforms/IPO/GlobalOpt.cpp
512–513

llvm test-suite did not show any regressions.

Generally speaking, big array accessed only through constant indexes and having less than 16 usages - looks like quite specialized use case.

rnk added a comment.Dec 30 2019, 11:28 AM

I think, in this case, we should fix the underlying problem. The pass already works like this:

  • check that all uses of GV are constant, inbounds GEPs
  • make new globals for each element in GV
  • re-iterate uses of GV, assert that each is a constant inbounds element access, replace access with new global for that index

We could make this more efficient by recording which elements are used during the initial safety check, and only making new globals for those. A bitvector indexed by element index, for example, would do the trick. This would allow us to, for your test case, delete all elements other than element 0, without excessive memory usage.

avl added a comment.Dec 30 2019, 12:09 PM

I started from the implementation similar to above description. But later I decided to avoid global SRA for big arrays, since big array with small number of usages is kind of artificial case. It is probably not worth to care about it too much. But, since that implementation was requested - I will update this patch with alternative implementation navigating through the usages and not-creating huge number of unused variables...

rnk added a comment.Dec 30 2019, 12:55 PM

I agree it's a bit of an artificial case, but this whole transform seems like an edge case in the first place. Removing the use count check would make it fire less often and make it even more of an edge case.

avl updated this revision to Diff 236036.Jan 3 2020, 5:49 AM

addressed comments(enumerate usages and create replacement variables for only used elements).

Unit tests: fail. 61175 tests passed, 1 failed and 729 were skipped.

failed: libc++.std/thread/thread_mutex/thread_mutex_requirements/thread_mutex_requirements_mutex/thread_mutex_class/try_lock.pass.cpp

clang-tidy: fail. Please fix clang-tidy findings.

clang-format: pass.

Build artifacts: diff.json, clang-tidy.txt, clang-format.patch, CMakeCache.txt, console-log.txt, test-results.xml

rnk accepted this revision.Jan 3 2020, 1:29 PM

lgtm with a small suggestion

llvm/lib/Transforms/IPO/GlobalOpt.cpp
488

I think this Globals variable isn't needed to later, so please sink it to reduce scope.

llvm/test/Transforms/GlobalOpt/long-compilation-global-sra.ll
1

Please check for the new global and absence of other globals.

This revision is now accepted and ready to land.Jan 3 2020, 1:29 PM
avl added a comment.Jan 3 2020, 2:05 PM

lgtm with a small suggestion

Ok, will land with this suggestion done.

As to above test failure: it looks like false alarm. It is not reproduced locally.

xbolva00 added inline comments.
llvm/lib/Transforms/IPO/GlobalOpt.cpp
440

isa

avl marked an inline comment as done.Jan 4 2020, 5:33 AM
This revision was automatically updated to reflect the committed changes.