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

[avl]

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.

[merge_guards_bot]

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

[avl]

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

[lebedev.ri]

llvm/lib/Transforms/IPO/GlobalOpt.cpp

512–513

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

[avl]

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]

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]

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]

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]

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

[merge_guards_bot]

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]

lgtm with a small suggestion

llvm/lib/Transforms/IPO/GlobalOpt.cpp

473

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

2

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

[avl]

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]

llvm/lib/Transforms/IPO/GlobalOpt.cpp

440

isa

llvm/lib/Transforms/IPO/GlobalOpt.cpp

static bool GlobalUsersSafeToSRA(GlobalValue *GV) {
 
   return true;
 }
 
 /// Copy over the debug info for a variable to its SRA replacements.
 static void transferSRADebugInfo(GlobalVariable *GV, GlobalVariable *NGV,
                                  uint64_t FragmentOffsetInBits,
                                  uint64_t FragmentSizeInBits,
                                  unsigned NumElements) {
   SmallVector<DIGlobalVariableExpression *, 1> GVs;
   GV->getDebugInfo(GVs);
   for (auto *GVE : GVs) {
     DIVariable *Var = GVE->getVariable();
     DIExpression *Expr = GVE->getExpression();
     if (NumElements > 1) {
       if (auto E = DIExpression::createFragmentExpression(
               Expr, FragmentOffsetInBits, FragmentSizeInBits))
static GlobalVariable *SRAGlobal(GlobalVariable *GV, const DataLayout &DL) {
   if (!GlobalUsersSafeToSRA(GV))
     return nullptr;
 
   assert(GV->hasLocalLinkage());
   Constant *Init = GV->getInitializer();
   Type *Ty = Init->getType();
 
   std::vector<GlobalVariable *> NewGlobals;
   Module::GlobalListType &Globals = GV->getParent()->getGlobalList();
 
   // Get the alignment of the global, either explicit or target-specific.
   unsigned StartAlignment = GV->getAlignment();
   if (StartAlignment == 0)
     StartAlignment = DL.getABITypeAlignment(GV->getType());
 
   if (StructType *STy = dyn_cast<StructType>(Ty)) {
     unsigned NumElements = STy->getNumElements();
for (unsigned i = 0, e = NumElements; i != e; ++i) {
 
       // Copy over the debug info for the variable.
       uint64_t Size = DL.getTypeAllocSizeInBits(NGV->getValueType());
       uint64_t FragmentOffsetInBits = Layout.getElementOffsetInBits(i);
       transferSRADebugInfo(GV, NGV, FragmentOffsetInBits, Size, NumElements);
     }
   } else if (SequentialType *STy = dyn_cast<SequentialType>(Ty)) {
     unsigned NumElements = STy->getNumElements();
-    if (NumElements > 16 && GV->hasNUsesOrMore(16))
+    if (NumElements > 16)
       return nullptr; // It's not worth it.
     NewGlobals.reserve(NumElements);
     auto ElTy = STy->getElementType();
     uint64_t EltSize = DL.getTypeAllocSize(ElTy);
     Align EltAlign(DL.getABITypeAlignment(ElTy));
     uint64_t FragmentSizeInBits = DL.getTypeAllocSizeInBits(ElTy);
     for (unsigned i = 0, e = NumElements; i != e; ++i) {
       Constant *In = Init->getAggregateElement(i);
       assert(In && "Couldn't get element of initializer?");

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

+; RUN: opt %s --O0 -globalopt -S -o -
+
+; This is a regression test against very slow execution...
+; In bad case it should fail by timeout.
+
+; Hand-reduced from this example.
+; clang++ -mllvm -disable-llvm-optzns
+
+;#include <stdio.h>
+;
+;namespace {
+;  char LargeBuffer[64 * 1024 * 1024];
+;}
+;
+;int main ( void ) {
+;
+;    LargeBuffer[0] = 0;
+;
+;    printf("");
+;
+;    return LargeBuffer[0] == 0;
+;}
+
+; ModuleID = 'test.cpp'
+source_filename = "test.cpp"
+target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+@_ZN12_GLOBAL__N_111LargeBufferE = internal global [67108864 x i8] zeroinitializer, align 16
+@.str = private unnamed_addr constant [1 x i8] c"\00", align 1
+
+; Function Attrs: norecurse uwtable
+define dso_local i32 @main() #0 {
+  %1 = alloca i32, align 4
+  store i32 0, i32* %1, align 4
+  store i8 0, i8* getelementptr inbounds ([67108864 x i8], [67108864 x i8]* @_ZN12_GLOBAL__N_111LargeBufferE, i64 0, i64 0), align 16
+  %2 = call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([1 x i8], [1 x i8]* @.str, i64 0, i64 0))
+  %3 = load i8, i8* getelementptr inbounds ([67108864 x i8], [67108864 x i8]* @_ZN12_GLOBAL__N_111LargeBufferE, i64 0, i64 0), align 16
+  %4 = sext i8 %3 to i32
+  %5 = icmp eq i32 %4, 0
+  %6 = zext i1 %5 to i32
+  ret i32 %6
+}
+
+declare dso_local i32 @printf(i8*, ...) #0
+
+attributes #0 = { norecurse uwtable }
+
+!llvm.module.flags = !{!0}
+!llvm.ident = !{!1}
+
+!0 = !{i32 1, !"wchar_size", i32 4}
+!1 = !{!"clang version 10.0.0 "}