[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

486

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

for (User *U : GV->users()) {
     // Check the gep and it's users are safe to SRA
     if (!isSafeSROAGEP(U))
       return false;
   }
 
   return true;
 }
 
+static bool CanDoGlobalSRA(GlobalVariable *GV) {
+  Constant *Init = GV->getInitializer();
+
+  if (isa<StructType>(Init->getType())) {
+    // nothing to check
+  } else if (SequentialType *STy = dyn_cast<SequentialType>(Init->getType())) {
+    if (STy->getNumElements() > 16 && GV->hasNUsesOrMore(16))
+      return false; // It's not worth it.
+  } else
+    return false;
+
+  return GlobalUsersSafeToSRA(GV);
+}
+
 /// 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) {

 
 /// Perform scalar replacement of aggregates on the specified global variable.
 /// This opens the door for other optimizations by exposing the behavior of the
 /// program in a more fine-grained way.  We have determined that this
 /// transformation is safe already.  We return the first global variable we
 /// insert so that the caller can reprocess it.
 static GlobalVariable *SRAGlobal(GlobalVariable *GV, const DataLayout &DL) {
   // Make sure this global only has simple uses that we can SRA.
-  if (!GlobalUsersSafeToSRA(GV))
+  if (!CanDoGlobalSRA(GV))
     return nullptr;
 
   assert(GV->hasLocalLinkage());
   Constant *Init = GV->getInitializer();
   Type *Ty = Init->getType();
 
-  std::vector<GlobalVariable *> NewGlobals;
-  Module::GlobalListType &Globals = GV->getParent()->getGlobalList();
+  std::map<unsigned, GlobalVariable *> NewGlobals;
 
   // 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();
-    NewGlobals.reserve(NumElements);
-    const StructLayout &Layout = *DL.getStructLayout(STy);
-    for (unsigned i = 0, e = NumElements; i != e; ++i) {
-      Constant *In = Init->getAggregateElement(i);
-      assert(In && "Couldn't get element of initializer?");
-      GlobalVariable *NGV = new GlobalVariable(STy->getElementType(i), false,
-                                               GlobalVariable::InternalLinkage,
-                                               In, GV->getName()+"."+Twine(i),
-                                               GV->getThreadLocalMode(),
-                                              GV->getType()->getAddressSpace());
-      NGV->setExternallyInitialized(GV->isExternallyInitialized());
-      NGV->copyAttributesFrom(GV);
-      Globals.push_back(NGV);
-      NewGlobals.push_back(NGV);
+  // Loop over all users and create replacement variables for used aggregate
+  // elements.
+  for (User *GEP : GV->users()) {
+    assert(((isa<ConstantExpr>(GEP) && cast<ConstantExpr>(GEP)->getOpcode() ==
+                                           Instruction::GetElementPtr) ||
+            isa<GetElementPtrInst>(GEP)) &&
+           "NonGEP CE's are not SRAable!");
+
+    // Ignore the 1th operand, which has to be zero or else the program is quite
+    // broken (undefined).  Get the 2nd operand, which is the structure or array
+    // index.
+    unsigned ElementIdx = cast<ConstantInt>(GEP->getOperand(2))->getZExtValue();
+    if (NewGlobals.count(ElementIdx) == 1)
+      continue; // we`ve already created replacement variable
+    assert(NewGlobals.count(ElementIdx) == 0);
+
+    Type *ElTy = nullptr;
+    if (StructType *STy = dyn_cast<StructType>(Ty))
+      ElTy = STy->getElementType(ElementIdx);
+    else if (SequentialType *STy = dyn_cast<SequentialType>(Ty))
+      ElTy = STy->getElementType();
+    assert(ElTy);
+
+    Constant *In = Init->getAggregateElement(ElementIdx);
+
+    GlobalVariable *NGV = new GlobalVariable(
+        ElTy, false, GlobalVariable::InternalLinkage, In,
+        GV->getName() + "." + Twine(ElementIdx), GV->getThreadLocalMode(),
+    NewGlobals.insert(std::make_pair(ElementIdx, NGV));
+
+    if (StructType *STy = dyn_cast<StructType>(Ty)) {
+      const StructLayout &Layout = *DL.getStructLayout(STy);
 
       // Calculate the known alignment of the field.  If the original aggregate
       // had 256 byte alignment for example, something might depend on that:
       // propagate info to each field.
-      uint64_t FieldOffset = Layout.getElementOffset(i);
+      uint64_t FieldOffset = Layout.getElementOffset(ElementIdx);
       Align NewAlign(MinAlign(StartAlignment, FieldOffset));
-      if (NewAlign > Align(DL.getABITypeAlignment(STy->getElementType(i))))
+      if (NewAlign >
+          Align(DL.getABITypeAlignment(STy->getElementType(ElementIdx))))
         NGV->setAlignment(NewAlign);
 
       // 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);
-    }
+      uint64_t FragmentOffsetInBits = Layout.getElementOffsetInBits(ElementIdx);
+      transferSRADebugInfo(GV, NGV, FragmentOffsetInBits, Size,
+                           STy->getNumElements());
     } else if (SequentialType *STy = dyn_cast<SequentialType>(Ty)) {
-    unsigned NumElements = STy->getNumElements();
-    if (NumElements > 16 && GV->hasNUsesOrMore(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?");
-
-      GlobalVariable *NGV = new GlobalVariable(STy->getElementType(), false,
-                                               GlobalVariable::InternalLinkage,
-                                               In, GV->getName()+"."+Twine(i),
-                                               GV->getThreadLocalMode(),
-                                              GV->getType()->getAddressSpace());
-      NGV->setExternallyInitialized(GV->isExternallyInitialized());
-      NGV->copyAttributesFrom(GV);
-      Globals.push_back(NGV);
-      NewGlobals.push_back(NGV);
 
       // Calculate the known alignment of the field.  If the original aggregate
       // had 256 byte alignment for example, something might depend on that:
       // propagate info to each field.
-      Align NewAlign(MinAlign(StartAlignment, EltSize * i));
+      Align NewAlign(MinAlign(StartAlignment, EltSize * ElementIdx));
       if (NewAlign > EltAlign)
         NGV->setAlignment(NewAlign);
-      transferSRADebugInfo(GV, NGV, FragmentSizeInBits * i, FragmentSizeInBits,
-                           NumElements);
+      transferSRADebugInfo(GV, NGV, FragmentSizeInBits * ElementIdx,
+                           FragmentSizeInBits, STy->getNumElements());
     }
   }
 
   if (NewGlobals.empty())
     return nullptr;
 
+  Module::GlobalListType &Globals = GV->getParent()->getGlobalList();
+  for (auto NewGlobalVar : NewGlobals)
+    Globals.push_back(NewGlobalVar.second);
+
   LLVM_DEBUG(dbgs() << "PERFORMING GLOBAL SRA ON: " << *GV << "\n");
 
   Constant *NullInt =Constant::getNullValue(Type::getInt32Ty(GV->getContext()));
 
   // Loop over all of the uses of the global, replacing the constantexpr geps,
   // with smaller constantexpr geps or direct references.
   while (!GV->use_empty()) {
     User *GEP = GV->user_back();
     assert(((isa<ConstantExpr>(GEP) &&
              cast<ConstantExpr>(GEP)->getOpcode()==Instruction::GetElementPtr)||
             isa<GetElementPtrInst>(GEP)) && "NonGEP CE's are not SRAable!");
 
     // Ignore the 1th operand, which has to be zero or else the program is quite
     // broken (undefined).  Get the 2nd operand, which is the structure or array
     // index.
-    unsigned Val = cast<ConstantInt>(GEP->getOperand(2))->getZExtValue();
-    if (Val >= NewGlobals.size()) Val = 0; // Out of bound array access.
+    unsigned ElementIdx = cast<ConstantInt>(GEP->getOperand(2))->getZExtValue();
+    assert(NewGlobals.count(ElementIdx) == 1);
 
-    Value *NewPtr = NewGlobals[Val];
-    Type *NewTy = NewGlobals[Val]->getValueType();
+    Value *NewPtr = NewGlobals[ElementIdx];
+    Type *NewTy = NewGlobals[ElementIdx]->getValueType();
 
     // Form a shorter GEP if needed.
     if (GEP->getNumOperands() > 3) {
       if (ConstantExpr *CE = dyn_cast<ConstantExpr>(GEP)) {
         SmallVector<Constant*, 8> Idxs;
         Idxs.push_back(NullInt);
         for (unsigned i = 3, e = CE->getNumOperands(); i != e; ++i)
           Idxs.push_back(CE->getOperand(i));
         NewPtr =
             ConstantExpr::getGetElementPtr(NewTy, cast<Constant>(NewPtr), Idxs);
       } else {
         GetElementPtrInst *GEPI = cast<GetElementPtrInst>(GEP);
         SmallVector<Value*, 8> Idxs;
         Idxs.push_back(NullInt);
         for (unsigned i = 3, e = GEPI->getNumOperands(); i != e; ++i)
           Idxs.push_back(GEPI->getOperand(i));
         NewPtr = GetElementPtrInst::Create(
-            NewTy, NewPtr, Idxs, GEPI->getName() + "." + Twine(Val), GEPI);
+            NewTy, NewPtr, Idxs, GEPI->getName() + "." + Twine(ElementIdx),
+            GEPI);
       }
     }
     GEP->replaceAllUsesWith(NewPtr);
 
     if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(GEP))
       GEPI->eraseFromParent();
     else
       cast<ConstantExpr>(GEP)->destroyConstant();
   }
 
   // Delete the old global, now that it is dead.
   Globals.erase(GV);
   ++NumSRA;
 
-  // Loop over the new globals array deleting any globals that are obviously
-  // dead.  This can arise due to scalarization of a structure or an array that
-  // has elements that are dead.
-  unsigned FirstGlobal = 0;
-  for (unsigned i = 0, e = NewGlobals.size(); i != e; ++i)
-    if (NewGlobals[i]->use_empty()) {
-      Globals.erase(NewGlobals[i]);
-      if (FirstGlobal == i) ++FirstGlobal;
-    }
-
-  return FirstGlobal != NewGlobals.size() ? NewGlobals[FirstGlobal] : nullptr;
+  assert(NewGlobals.size() > 0);
+  return NewGlobals.begin()->second;
 }
 
 /// Return true if all users of the specified value will trap if the value is
 /// dynamically null.  PHIs keeps track of any phi nodes we've seen to avoid
 /// reprocessing them.
 static bool AllUsesOfValueWillTrapIfNull(const Value *V,
                                         SmallPtrSetImpl<const PHINode*> &PHIs) {
   for (const User *U : V->users()) {

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;
+;}
+
+; check that global array LargeBufferE was optimized out
+; and local variable LargeBufferE.0 was used instead.
+
+; CHECK-NOT: global
+; CHECK: main()
+; CHECK-NEXT: LargeBufferE.0
+; CHECK-NOT: global
+
+; 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"
+
+@LargeBufferE = 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]* @LargeBufferE, 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]* @LargeBufferE, 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 "}