[GlobalOpt] Demote globals to locals more aggressively

[jmolloy]

Summary

Global to local demotion can speed up programs that use globals a lot. It is particularly useful with LTO, when the entire call graph is known and most functions have been internalized.

For a global to be demoted, it must only be accessed by one function and that function:

1. Must never recurse directly or indirectly, else the GV would be clobbered.
2. Must never rely on the value in GV at the start of the function (apart from the initializer).

GlobalOpt can already do this, but it is hamstrung and only ever tries to demote globals inside "main", because C++ gives extra guarantees about how main is called - once and only once.

In LTO mode, we can often prove the first property (if the function is internal by this point, we know enough about the callgraph to determine if it could possibly recurse).

The second property can be proven for a subset of functions by proving that all loads from GV are dominated by a store to GV. This is conservative in the name of compile time - this only requires a DominatorTree which is fairly cheap in the grand scheme of things. We could do more fancy stuff with MemoryDependenceAnalysis too to catch more cases but this appears to catch most of the useful ones in my testing.

Some of the churn in this patch is due to reordering the optimizations that get done on globals. We were trying to demote first, and if that failed we were trying to delete the global. Now that we can demote on more occasions, actually demotion isn't as powerful as deletion so we need to swap these around to keep tests passing and not pessimize code.

[jmolloy]

test/Transforms/GlobalOpt/2009-11-16-MallocSingleStoreToGlobalVar.ll

11 ↗

(On Diff #38658)

This is an unneeded change and will not be committed.

[majnemer]

lib/Transforms/IPO/GlobalOpt.cpp

1733

This is not true if the program is not a C++ program. main can be recursively called in C. Also, the name main may be reused for a function other than the entry point if it is not a hosted program which would be important to LTO something like the Linux kernel.

At the very least, we should check the functions prototype.

1772

auto *I

1789

auto *LI

[manmanren]

Thanks for working on this! Do you have any performance number?

lib/Transforms/IPO/GlobalOpt.cpp

95

Comments will be great.
It is a little strange to name it "FunctionsKnownNotToRecurse" with a bool that tells if the function will recurse.

1751

I am not sure if these conditions are sufficient to say the function does not recurse. Are indirect calls handled conservatively in the call graph?

[mehdi_amini]

lib/Transforms/IPO/GlobalOpt.cpp

1731

Note: I believe this is equivalent to

return !std::any_of(CGN->begin(), CGN->end(), [&] (CallGraphNode::CallRecord &CR) { return CR.second == CGN });

1738

Whether we go with an attribute (which I would support a priori) or not, it seems cleaner to expose the result of this through a module level analyses.

1748

Could the check !F be an assert or are there legitimate cases for this?

1786

I don't get this part, even if the load is larger than the GV you should have a must alias. Isn't the opposite case that is problematic?

Edit: reading later I think I figured: you need to makes sure that every load can be replace by the value forwarded from another store. I'm not sure "must alias" is the best wording here.

LLVM defines: The MustAlias response may only be returned if the two memory objects are guaranteed to always start at exactly the same location. A MustAlias response implies that the pointers compare equal.

1800

No else, just return.

1820

It would be nice if SmallVector (and other ADT) would allow to test a predicate on their content, this pattern would be less verbose. In the meantime I guess we're left with something like:

if(!std::any_of(Stores.begin(), Stores.end(), [&] (Instruction *S) { return DT.dominates(S, L); })
  return false;

If you're not allergic to the STL, or alternatively you may outline this like you did for functionDoesNotCallItself.

1916

So you moved this optimization a after all the previous one (like TryToShrinkGlobalToBoolean, OptimizeOnceStoredGlobal, ...), why?

1978

F->eraseFromParent(); is pretty straightforward and usual, this could deserve a comment.

[mehdi_amini]

And thanks for working on this! We were talking internally about improving GlobalOpt just two weeks ago on this aspect of recursive function detection :)

[jmolloy]

Hi guys,

Thanks for all the swift feedback. I have proposed adding a new "norecurse" function attribute in D14227, and uploaded a patch to FunctionAttrs to populate it in D14228. This patch now depends on those.

David, I agree the "main" hack is indeed a hack. The new "norecurse" attribute allows us to completely remove it as you say by teaching Clang to emit it during codegen for main() in C++ mode. I'll do that in a followup patch when the new attribute is committed and the dust has settled, if that's OK?

Mehdi, I've taken hopefully all your comments on board with this new version. One thing to comment on though:

So you moved this optimization a after all the previous one (like TryToShrinkGlobalToBoolean, OptimizeOnceStoredGlobal, ...), why?

I mentioned this in the description above, but basically it's because demoting globals to locals is less of a powerful optimization than deleting them outright (or shrinking them). With this patch global demotion triggers more often, so if we're not careful we could demote a global to a local that could have been deleted instead. That's why I changed the ordering.

James

[jmolloy]

Hi Manman, Mehdi,

Updated patch attached.

• Now, Clang knows how to add norecurse to "main", so we can remove that logic (hooray!)
• Removed all the norecurse logic, replaced with a query to F->doesNotRecurse()

Please take a look.

Cheers,

James

[mehdi_amini]

Looks good, but the changes we discussed on IRC!

lib/Transforms/IPO/GlobalOpt.cpp

1767

To sum up our IRC conversation, we can unconditionally add Load and Stored to the arrays, and check for the size later: we only care if a load is covered by a store at least as large.

1789

Nitpick: current guideline is not to repeat the function name in the doxygen.

1829

Commit this separately now.

[jmolloy]

Hi Mehdi, Duncan, Manman,

I've updated the patch following all your comments. Implementing Mehdi's suggestion made the code look significantly neater and will also catch more cases.

I've also undone the reordering of optimizations in ProcessInternalGlobal, as I don't think this is now needed now that "main" isn't implicitly norecurse. It was only done to pacify tests in the first place, and they all pass now without modification.

Cheers,

James

[mehdi_amini]

lib/Transforms/IPO/GlobalOpt.cpp

1809

If the function does not recurse and is the only user of the global, why do we need isPointerValueDeadOnEntryToFunction?

[jmolloy]

Hi Duncan,

I had already committed after Mehdi's LGTM, so I have applied fixes based on your comments in r253192.

Cheers,

James

[jmolloy]

Hi All,

I just want to apologize - after rereading the phab comments here I realize that I actually mistook Mehdi's LGTM on D14228 for this review when looking at my backlog, so I committed it before it was fully approved.

To reply to Mehdi's comment specifically:

If the function does not recurse and is the only user of the global, why do we need isPointerValueDeadOnEntryToFunction?

Consider this:

static int g = 0;
int f() {
  printf("%d\n", g++);
}

g can obviously not be localized, and f does not recurse. However, each invocation of f depends on the previous invocation because g is read before being written. The "isPointerValueDeadOnEntry" function is there to ensure the function is idempotent with respect to the given global.

James

[mehdi_amini]

Hi,

[hfinkel]

(will close)

[hfinkel]

This was committed in r253168.

[hfinkel]

(It seems that, even after marking this as accepted, I cannot close it)

lib/Transforms/IPO/GlobalOpt.cpp

 #include "llvm/Analysis/ConstantFolding.h"
 #include "llvm/Analysis/MemoryBuiltins.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/IR/CallSite.h"
 #include "llvm/IR/CallingConv.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/DerivedTypes.h"
+#include "llvm/IR/Dominators.h"
 #include "llvm/IR/GetElementPtrTypeIterator.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/Module.h"
 #include "llvm/IR/Operator.h"
 #include "llvm/IR/ValueHandle.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/Debug.h"

 STATISTIC(NumAliasesResolved, "Number of global aliases resolved");
 STATISTIC(NumAliasesRemoved, "Number of global aliases eliminated");
 STATISTIC(NumCXXDtorsRemoved, "Number of global C++ destructors removed");
 
 namespace {
   struct GlobalOpt : public ModulePass {
     void getAnalysisUsage(AnalysisUsage &AU) const override {
       AU.addRequired<TargetLibraryInfoWrapperPass>();
+      AU.addRequired<DominatorTreeWrapperPass>();
     }
     static char ID; // Pass identification, replacement for typeid
     GlobalOpt() : ModulePass(ID) {
       initializeGlobalOptPass(*PassRegistry::getPassRegistry());
     }
 
     bool runOnModule(Module &M) override;
 
   private:
     bool OptimizeFunctions(Module &M);
     bool OptimizeGlobalVars(Module &M);
     bool OptimizeGlobalAliases(Module &M);
     bool ProcessGlobal(GlobalVariable *GV,Module::global_iterator &GVI);
     bool ProcessInternalGlobal(GlobalVariable *GV,Module::global_iterator &GVI,
                                const GlobalStatus &GS);
     bool OptimizeEmptyGlobalCXXDtors(Function *CXAAtExitFn);
     
+    bool isPointerValueDeadOnEntryToFunction(const Function *F, GlobalValue *GV);
+    
     TargetLibraryInfo *TLI;
     SmallSet<const Comdat *, 8> NotDiscardableComdats;
   };
 }
 
 char GlobalOpt::ID = 0;
 INITIALIZE_PASS_BEGIN(GlobalOpt, "globalopt",
                 "Global Variable Optimizer", false, false)
 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
+INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
 INITIALIZE_PASS_END(GlobalOpt, "globalopt",
                 "Global Variable Optimizer", false, false)
 
 ModulePass *llvm::createGlobalOptimizerPass() { return new GlobalOpt(); }
 
 /// Is this global variable possibly used by a leak checker as a root?  If so,
 /// we might not really want to eliminate the stores to it.
 static bool isLeakCheckerRoot(GlobalVariable *GV) {
bool GlobalOpt::ProcessGlobal(GlobalVariable *GV,
   }
 
   if (GV->isConstant() || !GV->hasInitializer())
     return false;
 
   return ProcessInternalGlobal(GV, GVI, GS);
 }
 
+bool GlobalOpt::isPointerValueDeadOnEntryToFunction(const Function *F, GlobalValue *GV) {
+  // Find all uses of GV. We expect them all to be in F, and if we can't
+  // identify any of the uses we bail out.
+  //
+  // On each of these uses, identify if the memory that GV points to is
+  // used/required/live at the start of the function. If it is not, for example
+  // if the first thing the function does is store to the GV, the GV can
+  // possibly be demoted.
+  //
+  // We don't do an exhaustive search for memory operations - simply look
+  // through bitcasts as they're quite common and benign.
+  const DataLayout &DL = GV->getParent()->getDataLayout();
+  SmallVector<LoadInst *, 4> Loads;
+  SmallVector<StoreInst *, 4> Stores;
+  for (auto *U : GV->users()) {
+    if (Operator::getOpcode(U) == Instruction::BitCast) {
+      for (auto *UU : U->users()) {
+        if (auto *LI = dyn_cast<LoadInst>(UU))
+          Loads.push_back(LI);
+        else if (auto *SI = dyn_cast<StoreInst>(UU))
+          Stores.push_back(SI);
+        else
+          return false;
+      }
+      continue;
+    }
+
+    Instruction *I = dyn_cast<Instruction>(U);
+    if (!I)
+      return false;
+    assert(I->getParent()->getParent() == F);
+
+    if (auto *LI = dyn_cast<LoadInst>(I))
+      Loads.push_back(LI);
+    else if (auto *SI = dyn_cast<StoreInst>(I))
+      Stores.push_back(SI);
+    else
+      return false;
+  }
+
+  // We have identified all uses of GV into loads and stores. Now check if all
+  // of them are known not to depend on the value of the global at the function
+  // entry point. We do this by ensuring that every load is dominated by at
+  // least one store.
+  auto &DT = getAnalysis<DominatorTreeWrapperPass>(*const_cast<Function *>(F))
+                 .getDomTree();
+
+  for (auto *L : Loads) {
+    auto *LTy = L->getType();
+    if (!std::any_of(Stores.begin(), Stores.end(), [&](StoreInst *S) {
+          auto *STy = S->getValueOperand()->getType();
+          // The load is only dominated by the store if DomTree says so
+          // and the number of bits loaded in L is less than or equal to
+          // the number of bits stored in S.
+          return DT.dominates(S, L) &&
+                 DL.getTypeStoreSize(LTy) <= DL.getTypeStoreSize(STy);
+        }))
+      return false;
+  }
+  // All loads have known dependences inside F, so the global can be localized.
+  return true;
+}
+
 /// Analyze the specified global variable and optimize
 /// it if possible.  If we make a change, return true.
 bool GlobalOpt::ProcessInternalGlobal(GlobalVariable *GV,
                                       Module::global_iterator &GVI,
                                       const GlobalStatus &GS) {
   auto &DL = GV->getParent()->getDataLayout();
-  // If this is a first class global and has only one accessing function
-  // and this function is main (which we know is not recursive), we replace
-  // the global with a local alloca in this function.
+  // If this is a first class global and has only one accessing function and
+  // this function is non-recursive, we replace the global with a local alloca
+  // in this function.
   //
   // NOTE: It doesn't make sense to promote non-single-value types since we
   // are just replacing static memory to stack memory.
   //
   // If the global is in different address space, don't bring it to stack.
   if (!GS.HasMultipleAccessingFunctions &&
       GS.AccessingFunction && !GS.HasNonInstructionUser &&
       GV->getType()->getElementType()->isSingleValueType() &&
-      GS.AccessingFunction->getName() == "main" &&
-      GS.AccessingFunction->hasExternalLinkage() &&
-      GV->getType()->getAddressSpace() == 0) {
+      GV->getType()->getAddressSpace() == 0 &&
+      !GV->isExternallyInitialized() &&
+      GS.AccessingFunction->doesNotRecurse() &&
+      isPointerValueDeadOnEntryToFunction(GS.AccessingFunction, GV) ) {
     DEBUG(dbgs() << "LOCALIZING GLOBAL: " << *GV << "\n");
     Instruction &FirstI = const_cast<Instruction&>(*GS.AccessingFunction
                                                    ->getEntryBlock().begin());
     Type *ElemTy = GV->getType()->getElementType();
     // FIXME: Pass Global's alignment when globals have alignment
     AllocaInst *Alloca = new AllocaInst(ElemTy, nullptr,
                                         GV->getName(), &FirstI);
     if (!isa<UndefValue>(GV->getInitializer()))
       new StoreInst(GV->getInitializer(), Alloca, &FirstI);
 
     GV->replaceAllUsesWith(Alloca);
     GV->eraseFromParent();
     ++NumLocalized;
     return true;
   }
 
   // If the global is never loaded (but may be stored to), it is dead.
   // Delete it now.
   if (!GS.IsLoaded) {
     DEBUG(dbgs() << "GLOBAL NEVER LOADED: " << *GV << "\n");
 
     bool Changed;
     if (isLeakCheckerRoot(GV)) {
       // Delete any constant stores to the global.
       Changed = CleanupPointerRootUsers(GV, TLI);
     } else {
       // Delete any stores we can find to the global.  We may not be able to
       // make it completely dead though.
if (Constant *SOVConstant = dyn_cast<Constant>(GS.StoredOnceValue)) {
           ++NumShrunkToBool;
           return true;
         }
       }
     }
   }
 
   return false;
 }
 
 /// Walk all of the direct calls of the specified function, changing them to
 /// FastCC.
 static void ChangeCalleesToFastCall(Function *F) {
   for (User *U : F->users()) {
     if (isa<BlockAddress>(U))
       continue;
     CallSite CS(cast<Instruction>(U));
for (Module::iterator FI = M.begin(), E = M.end(); FI != E; ) {
 
     const Comdat *C = F->getComdat();
     bool inComdat = C && NotDiscardableComdats.count(C);
     F->removeDeadConstantUsers();
     if ((!inComdat || F->hasLocalLinkage()) && F->isDefTriviallyDead()) {
       F->eraseFromParent();
       Changed = true;
       ++NumFnDeleted;
     } else if (F->hasLocalLinkage()) {
       if (isProfitableToMakeFastCC(F) && !F->isVarArg() &&
           !F->hasAddressTaken()) {
         // If this function has a calling convention worth changing, is not a
         // varargs function, and is only called directly, promote it to use the
         // Fast calling convention.
         F->setCallingConv(CallingConv::Fast);
         ChangeCalleesToFastCall(F);
         ++NumFastCallFns;

test/Transforms/GlobalOpt/global-demotion.ll

+; RUN: opt -globalopt -S < %s | FileCheck %s
+
+@G1 = internal global i32 5
+@G2 = internal global i32 5
+@G3 = internal global i32 5
+@G4 = internal global i32 5
+@G5 = internal global i32 5
+
+; CHECK-LABEL: @test1
+define internal i32 @test1() norecurse {
+; CHECK-NOT: @G1
+  store i32 4, i32* @G1
+  %a = load i32, i32* @G1
+; CHECK: ret
+  ret i32 %a
+}
+
+; The load comes before the store which makes @G2 live before the call.
+; CHECK-LABEL: @test2
+define internal i32 @test2() norecurse {
+; CHECK-NOT: %G2
+  %a = load i32, i32* @G2
+  store i32 4, i32* @G2
+; CHECK: ret
+  ret i32 %a
+}
+
+; This global is indexed by a GEP - this makes it partial alias and we bail out.
+; FIXME: We don't actually have to bail out in this case.
+
+; CHECK-LABEL: @test3
+define internal i32 @test3() norecurse {
+; CHECK-NOT: %G3
+  %x = getelementptr i32,i32* @G3, i32 0
+  %a = load i32, i32* %x
+  store i32 4, i32* @G3
+; CHECK: ret
+  ret i32 %a
+}
+
+; The global is casted away to a larger type then loaded. The store only partially
+; covers the load, so we must not demote.
+
+; CHECK-LABEL: @test4
+define internal i32 @test4() norecurse {
+; CHECK-NOT: %G4
+  store i32 4, i32* @G4
+  %x = bitcast i32* @G4 to i64*
+  %a = load i64, i64* %x
+  %b = trunc i64 %a to i32
+; CHECK: ret
+  ret i32 %b
+}
+
+; The global is casted away to a smaller type then loaded. This one is fine.
+
+; CHECK-LABEL: @test5
+define internal i32 @test5() norecurse {
+; CHECK-NOT: @G5
+  store i32 4, i32* @G5
+  %x = bitcast i32* @G5 to i16*
+  %a = load i16, i16* %x
+  %b = zext i16 %a to i32
+; CHECK: ret
+  ret i32 %b
+}
+
+define i32 @main() norecurse {
+  %a = call i32 @test1()
+  %b = call i32 @test2()
+  %c = call i32 @test3()
+  %d = call i32 @test4()
+  %e = call i32 @test5()
+
+  %x = or i32 %a, %b
+  %y = or i32 %x, %c
+  %z = or i32 %y, %d
+  %w = or i32 %z, %e
+  ret i32 %w
+}

test/Transforms/GlobalOpt/metadata.ll

 ; RUN: opt -S -globalopt < %s | FileCheck %s
 
 ; PR6112 - When globalopt does RAUW(@G, %G), the metadata reference should drop
 ; to null.  Function local metadata that references @G from a different function
 ; to that containing %G should likewise drop to null.
 @G = internal global i8** null
 
-define i32 @main(i32 %argc, i8** %argv) {
+define i32 @main(i32 %argc, i8** %argv) norecurse {
 ; CHECK-LABEL: @main(
 ; CHECK: %G = alloca
   store i8** %argv, i8*** @G
   ret i32 0
 }
 
 define void @foo(i32 %x) {
 ; Note: these arguments look like MDNodes, but they're really syntactic sugar

test/Transforms/MergeFunc/crash2.ll

 ; RUN: opt %s -mergefunc -globalopt -S -o - | FileCheck %s
 
 ; Make sure we don't crash on this example. This test is supposed to test that
 ; MergeFunctions clears its GlobalNumbers value map. If this map still contains
 ; entries when running globalopt and the MergeFunctions instance is still alive
 ; the optimization of @G would cause an assert because globalopt would do an
 ; RAUW on @G which still exists as an entry in the GlobalNumbers ValueMap which
 ; causes an assert in the ValueHandle call back because we are RAUWing with a
 ; different type (AllocaInst) than its key type (GlobalValue).
 
 @G = internal global i8** null
 @G2 = internal global i8** null
 
-define i32 @main(i32 %argc, i8** %argv) {
+define i32 @main(i32 %argc, i8** %argv) norecurse {
 ; CHECK: alloca
   store i8** %argv, i8*** @G
   ret i32 0
 }
 
 define internal i8** @dead1(i64 %p) {
   call void @right(i64 %p)
   call void @right(i64 %p)