Extend the use of @llvm.invariant.start/end intrinsics for GVN-based load elimination purposes to also handle global variables.

[lvoufo]

Summary

The -globalopt pass is made to require -invariant-info-marker, similarly to -gvn. (Note: Both -gvn and -globalopt require basic AA.)

The test case is also expanded to illustrate the subtle nuances and expected similarities between local and global variables.

[lvoufo]

Fix typo in patch.

[nlewycky]

lib/Transforms/IPO/GlobalOpt.cpp

2838–2839

I think the usual way to write this is like:

CallSite CS(&*CurInst);
if (CS) {

2844

DbgInfoIntrinsics are Intrinsics, you don't need to test for them separately. Also remove "..." because there aren't any more things being checked here.

2848

Isn't this a double-increment? You'll skip CurInst here, then the for loop increment will skip whatever instruction comes after?

2875–2880

This doesn't explain what goes wrong if evaluation does fail part way through.

I think the point is that the optimization is for the case where we have an invariant.start with no invariant.end, and if EvaluateBlock terminates early we don't know whether there is an invariant.end matching our invariant.start.

But there's a much easier way to do this, the invariant.end must directly use its invariant.start ... so if the invariant.start has zero users then there is no end, otherwise there is an end. Now, I thought that optimization was already implemented which brings me to the test.

2881

I'm deeply confused. This appears to populate InvInfo, but we never seem to use it for optimization?

Are you using this to populate InvInfo so that GVN can use it?

test/Transforms/LoadElim/invariant.ll

39

This function is never called, and thus should never be examined by GlobalOpt's Evaluate calls at all, right?

I notice you're doing -globalopt -gvn. Please split GVN tests and GlobalOpt tests apart and add new changes testing globalopt only for changes to globalopt. If you need to verify that the combination of passes works well, you would add it to test/Transforms/PhaseOrdering, but I don't think that's necessary here.

[lvoufo]

lib/Transforms/IPO/GlobalOpt.cpp

2848

Yes, it is. Oops. Thanks for the catch!

2875–2880

This only cares about marking global variables before evaluating constructors. Whether evaluation fails or not should have no bearing on the fact that a given global variable is only-readable 'writeonce'. Besides, we also do not have to worry about invariant.end here because a global variable never stops being 'writeonce' once marked as such.

2881

Correct.

test/Transforms/LoadElim/invariant.ll

39

I'm confused. This *is* supposed to test the effect of changes to -globalopt for -gvn...

[lvoufo]

To summarize my thoughts after these comments, this is an analysis that should be kept outside of -globalopt, since it does not affect the logic of -globalopt at all... So, I'm working on that.

lib/Transforms/IPO/GlobalOpt.cpp

 #include "llvm/Transforms/IPO.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/ConstantFolding.h"
+#include "llvm/Analysis/InvariantInfo.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"

 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<InvariantInfoMarkerPass>();
       AU.addRequired<DominatorTreeWrapperPass>();
     }
     static char ID; // Pass identification, replacement for typeid
     GlobalOpt() : ModulePass(ID) {
       initializeGlobalOptPass(*PassRegistry::getPassRegistry());
     }
 
     bool runOnModule(Module &M) override;
private:
     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(InvariantInfoMarkerPass)
 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.
for (CurInst = NextBB->begin();
          (PN = dyn_cast<PHINode>(CurInst)); ++CurInst)
       setVal(PN, getVal(PN->getIncomingValueForBlock(CurBB)));
 
     // Advance to the next block.
     CurBB = NextBB;
   }
 }
 
+static void processInvariantIntrinsics(InvariantInfo &InvInfo, BasicBlock *BB);
+
+/// Process invariant intrinsics in the given function.
+static void processInvariantIntrinsics(InvariantInfo &InvInfo, Function *F) {
+  for (Function::iterator BB = F->begin(), BE = F->end(); BB != BE; ++BB)
+    processInvariantIntrinsics(InvInfo, &*BB);
+}
+
+/// Scan the given block to process invariant intrinsics, tracing whatever
+/// call chain that can be traced.
+void processInvariantIntrinsics(InvariantInfo &InvInfo, BasicBlock *BB) {
+  for (BasicBlock::iterator CurInst = BB->begin(), InstE = BB->end();
+       CurInst != InstE; ++CurInst) {
+    if (isa<CallInst>(CurInst) || isa<InvokeInst>(CurInst)) {
+      CallSite CS(&*CurInst);
+
+      if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(CurInst))
+        processInvariantIntrinsic(II, InvInfo);
+
+      // Ignore debug info, inline asm, intrinsics, ...
+      if (isa<DbgInfoIntrinsic>(CS.getInstruction()) ||
+          isa<InlineAsm>(CS.getCalledValue()) ||
+          dyn_cast<IntrinsicInst>(CS.getInstruction())) {
+        ++CurInst;
+        continue;
+      }
+
+      Function *Callee = CS.getCalledFunction();
+      if (Callee && !Callee->isDeclaration())
+        processInvariantIntrinsics(InvInfo, Callee);
+
+      if (InvokeInst *II = dyn_cast<InvokeInst>(CurInst)) {
+        for (unsigned i = 0; i < II->getNumSuccessors(); ++i)
+          processInvariantIntrinsics(InvInfo, II->getSuccessor(i));
+        break;
+      }
+    } else if (TerminatorInst *TI = dyn_cast<TerminatorInst>(CurInst)) {
+      for (unsigned i = 0; i < TI->getNumSuccessors(); ++i)
+        processInvariantIntrinsics(InvInfo, TI->getSuccessor(i));
+      break;
+    }
+  }
+}
+
 /// Evaluate static constructors in the function, if we can.  Return true if we
 /// can, false otherwise.
 static bool EvaluateStaticConstructor(Function *F, const DataLayout &DL,
-                                      const TargetLibraryInfo *TLI) {
+                                      const TargetLibraryInfo *TLI,
+                                      InvariantInfo &InvInfo) {
+
+  // Scan the function's blocks to process invariant (start) intrinsics.
+  // This will mark writeonce global variables as written, and is necessary to
+  // do here because EvaluateBlock(), via EvaluateFunction() (below), could
+  // exit before processing the invariant intrinsic call, e.g., if a call to
+  // a function declaration that we cannot constant fold occurs before the
+  // intrinsic call.
+  processInvariantIntrinsics(InvInfo, F);
+
   // Call the function.
   Evaluator Eval(DL, TLI);
   Constant *RetValDummy;
   bool EvalSuccess = Eval.EvaluateFunction(F, RetValDummy,
                                            SmallVector<Constant*, 0>());
 
   if (EvalSuccess) {
     ++NumCtorsEvaluated;
bool GlobalOpt::OptimizeEmptyGlobalCXXDtors(Function *CXAAtExitFn) {
   return Changed;
 }
 
 bool GlobalOpt::runOnModule(Module &M) {
   bool Changed = false;
 
   auto &DL = M.getDataLayout();
   TLI = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
+  auto &InvInfo = getAnalysis<InvariantInfoMarkerPass>().getInvariantInfo();
 
   bool LocalChange = true;
   while (LocalChange) {
     LocalChange = false;
 
     NotDiscardableComdats.clear();
     for (const GlobalVariable &GV : M.globals())
       if (const Comdat *C = GV.getComdat())
         if (!GV.isDiscardableIfUnused() || !GV.use_empty())
           NotDiscardableComdats.insert(C);
     for (Function &F : M)
       if (const Comdat *C = F.getComdat())
         if (!F.isDefTriviallyDead())
           NotDiscardableComdats.insert(C);
     for (GlobalAlias &GA : M.aliases())
       if (const Comdat *C = GA.getComdat())
         if (!GA.isDiscardableIfUnused() || !GA.use_empty())
           NotDiscardableComdats.insert(C);
 
     // Delete functions that are trivially dead, ccc -> fastcc
     LocalChange |= OptimizeFunctions(M);
 
     // Optimize global_ctors list.
     LocalChange |= optimizeGlobalCtorsList(M, [&](Function *F) {
-      return EvaluateStaticConstructor(F, DL, TLI);
+      return EvaluateStaticConstructor(F, DL, TLI, InvInfo);
     });
 
     // Optimize non-address-taken globals.
     LocalChange |= OptimizeGlobalVars(M);
 
     // Resolve aliases, when possible.
     LocalChange |= OptimizeGlobalAliases(M);
 

test/Transforms/LoadElim/invariant.ll

-; RUN: opt < %s -gvn -S | FileCheck %s
+; RUN: opt < %s -gvn -S | FileCheck %s --check-prefix=CHECKL --check-prefix=CHECK
+; RUN: opt < %s -globalopt -gvn -S | FileCheck %s --check-prefix=CHECKG --check-prefix=CHECK
 
 ; On a given pointer to allocated memory, invariant_start/end intrinsic
 ; calls indicate that the memory can be considered constant for load
 ; elimination purposes.
+
 define void @example() {
 entry:
   %i = alloca i32
   call void @foo(i32* %i)              ; #1
   %0 = bitcast i32* %i to i8*
   %1 = call {}* (i64, i8*) @llvm.invariant.start(i64 4, i8* %0)
   ; CHECK: call {{.*}}@llvm.invariant.start(i64 {{[0-9]+}}, i8*
   call void @foo(i32* %i)              ; #2
   %2 = load i32, i32* %i               ; Not clobbered by #2; Clobbered by #1; Unchanged.
   ; CHECK: load i32, i32*
   call void @bar(i32 %2)
   call void @foo(i32* %i)              ; #3
   %3 = load i32, i32* %i               ; Not clobbered by #3; Merged into %2. 
   ; CHECK-NOT: load i32, i32*
   call void @bar(i32 %3)
   call void @llvm.invariant.end({}* %1, i64 4, i8* %0)
   ; CHECK: call {{.*}}@llvm.invariant.end({{.*}}, i64 {{[0-9]+}}, i8*
   call void @foo(i32* %i)              ; #4
   %4 = load i32, i32* %i               ; Clobbered by #4; Unchanged. 
   ; CHECK: load i32, i32*
   call void @bar(i32 %4)
   ret void
 }
 
+; Example with a global variable instead of an alloca instruction,
+; with an invariant_start call during global construction and
+; with no invariant_end call.
+
+@gi = internal global i32 0
[e-mail]_ctors = appending global [1 x { i32, void ()*, i8* }] [{ i32, void ()*, i8* } { i32 65535, void ()* @global_constructor, i8* null }]
+
+define void @globalex() {
+entry:
+  call void @foo(i32* @gi)              ; #2
+  %0 = load i32, i32* @gi               ; Not clobbered by #2; Unknown dependence; Unchanged.
+  ; CHECK: load i32, i32*
+  call void @bar(i32 %0)
+  call void @foo(i32* @gi)              ; #3
+  %1 = load i32, i32* @gi               ; Not clobbered by #3; Merged into %0.
+  ; CHECKL: load i32, i32*
+  ; CHECKG-NOT: load i32, i32*
+  call void @bar(i32 %1)
+  call void @foo(i32* @gi)              ; #4
+  %2 = load i32, i32* @gi               ; Not clobbered by #4, nor #3; Merged into %0.
+  ; CHECKL: load i32, i32*
+  ; CHECKG-NOT: load i32, i32*
+  call void @bar(i32 %2)
+  ret void
+}
+
+define internal void @construct_gi() {
+entry:
+  call void @foo(i32* @gi)              ; #1 -- preserves load instructions from over-simplification.
+  %0 = bitcast i32* @gi to i8*
+  %1 = call {}* (i64, i8*) @llvm.invariant.start(i64 4, i8* %0)
+  ; CHECK: call {{.*}}@llvm.invariant.start(i64 {{[0-9]+}}, i8*
+  ret void
+}
+
+define internal void @global_constructor() {
+entry:
+  call void @construct_gi()
+  ret void
+}
+
+; Helper function declarations.
 declare void @bar(i32)
 declare void @foo(i32*)
 declare {}* @llvm.invariant.start(i64, i8* nocapture)
 declare void @llvm.invariant.end({}*, i64, i8* nocapture)