[GlobalOpt] Localize some globals that have non-instruction users

[jmolloy]

Summary

We currently bail out of global localization if the global has non-instruction users. However, often these can be simple bitcasts or constant-GEPs, which we can easily turn into instructions before localizing. Be a bit more aggressive.

[mehdi_amini]

LGTM with some comments.

lib/Transforms/IPO/GlobalOpt.cpp

1845

Nit: A common pattern is to put UUsers out of the loop and call clear at the end of each iteration. So that if you cross the limit of 4 multiple times you won't pay the dynamic allocation (and the copy) again.

1849

Minor suggestion: I'd rather read assert(isa<Instruction>) before cast<Instruction>

test/Transforms/GlobalOpt/localize-constexpr.ll

9

The last check is spurious. The next CHECK-LABEL should be enough I think.

[mehdi_amini]

r253584

lib/Transforms/IPO/GlobalOpt.cpp

   return true;
 }
 
+/// C may have non-instruction users. Can all of those users be turned into
+/// instructions?
+static bool allNonInstructionUsersCanBeMadeInstructions(Constant *C) {
+  // We don't do this exhaustively. The most common pattern that we really need
+  // to care about is a constant GEP or constant bitcast - so just looking
+  // through one single ConstantExpr.
+  //
+  // The set of constants that this function returns true for must be able to be
+  // handled by makeAllConstantUsesInstructions.
+  for (auto *U : C->users()) {
+    if (isa<Instruction>(U))
+      continue;
+    if (!isa<ConstantExpr>(U))
+      // Non instruction, non-constantexpr user; cannot convert this.
+      return false;
+    for (auto *UU : U->users())
+      if (!isa<Instruction>(UU))
+        // A constantexpr used by another constant. We don't try and recurse any
+        // further but just bail out at this point.
+        return false;
+  }
+
+  return true;
+}
+
+/// C may have non-instruction users, and
+/// allNonInstructionUsersCanBeMadeInstructions has returned true. Convert the
+/// non-instruction users to instructions.
+static void makeAllConstantUsesInstructions(Constant *C) {
+  SmallVector<ConstantExpr*,4> Users;
+  for (auto *U : C->users()) {
+    if (isa<ConstantExpr>(U))
+      Users.push_back(cast<ConstantExpr>(U));
+    else
+      // We should never get here; allNonInstructionUsersCanBeMadeInstructions
+      // should not have returned true for C.
+      assert(
+          isa<Instruction>(U) &&
+          "Can't transform non-constantexpr non-instruction to instruction!");
+  }
+  
+  for (auto *U : Users) {
+    SmallVector<Value*,4> UUsers;
+    for (auto *UU : U->users())
+      UUsers.push_back(UU);
+    for (auto *UU : UUsers) {
+      assert(!isa<Constant>(UU));
+
+      Instruction *UI = cast<Instruction>(UU);
+      Instruction *NewU = U->getAsInstruction();
+      NewU->insertBefore(UI);
+      UI->replaceUsesOfWith(U, NewU);
+    }
+    U->dropAllReferences();
+  }
+}
+
 /// Analyze the specified global variable and optimize
 /// it if possible.  If we make a change, return true.
 bool GlobalOpt::ProcessInternalGlobal(GlobalVariable *GV,

   //
   // If the global is in different address space, don't bring it to stack.
   if (!GS.HasMultipleAccessingFunctions &&
-      GS.AccessingFunction && !GS.HasNonInstructionUser &&
+      GS.AccessingFunction &&
       GV->getType()->getElementType()->isSingleValueType() &&
       GV->getType()->getAddressSpace() == 0 &&
       !GV->isExternallyInitialized() &&
+      allNonInstructionUsersCanBeMadeInstructions(GV) &&
       GS.AccessingFunction->doesNotRecurse() &&
       isPointerValueDeadOnEntryToFunction(GS.AccessingFunction, GV) ) {
     DEBUG(dbgs() << "LOCALIZING GLOBAL: " << *GV << "\n");

     if (!isa<UndefValue>(GV->getInitializer()))
       new StoreInst(GV->getInitializer(), Alloca, &FirstI);
 
+    makeAllConstantUsesInstructions(GV);
+    
     GV->replaceAllUsesWith(Alloca);
     GV->eraseFromParent();
     ++NumLocalized;

test/Transforms/GlobalOpt/localize-constexpr.ll

+; RUN: opt -S < %s -globalopt | FileCheck %s
+
+@G = internal global i32 42
+
+define i8 @f() norecurse {
+; CHECK-LABEL: @f
+; CHECK: alloca
+; CHECK-NOT: @G
+; CHECK: }
+  store i32 42, i32* @G
+  %a = load i8, i8* bitcast (i32* @G to i8*)
+  ret i8 %a
+}
+
+@H = internal global i32 42
+@Halias = internal alias i32, i32* @H
+
+; @H can't be localized because @Halias uses it, and @Halias can't be converted to an instruction.
+define i8 @g() norecurse {
+; CHECK-LABEL: @g
+; CHECK-NOT: alloca
+; CHECK: @H
+; CHECK: }
+  store i32 42, i32* @H
+  %a = load i8, i8* bitcast (i32* @H to i8*)
+  ret i8 %a
+}
+