New alias analysis for static global variables

[samparker]

Summary

Hi,

After comments and suggestions on my original patch, including being pointed to GlobalsModRef AA, I decided to model a new AA pass on GlobalsModRef but one that is more light weight than GlobalsModRef. This pass is designed to just track static global variables which we find are often used in embedded applications. Hal originally asked for better analysis of GlobalsModRef, so I have run LNT multiple times on my desktop, even runs are with this new pass and odd are without:

	        geometric mean

run compile time execution time
1 0.1219 0.0052
2 0.1071 0.0052
3 0.1085 0.0053
4 0.109 0.0055
5 0.1078 0.0052
6 0.108 0.0051
7 0.1078 0.0052
8 0.1085 0.0053
9 0.1067 0.0053
10 0.1073 0.0053
11 0.11 0.0053
12 0.1041 0.005
13 0.1073 0.0051
14 0.1085 0.0049
15 0.1079 0.0052
16 0.1072 0.0054
17 0.1057 0.0051
18 0.1074 0.0052
19 0.1074 0.005
20 0.1061 0.0052

Cheers,
Sam

[hfinkel]

The compile-time numbers look good (in the sense that there is no significant difference between the even- and odd-numbered runs).

Please comment on exactly what makes this lighter weight than GlobalsModRef AA, and why this should be a separate pass.

include/llvm/Analysis/Passes.h

27

This needs a comment like the others.

lib/Analysis/IPA/StaticGlobalsAA.cpp

28 ↗

(On Diff #26590)

You should collect some statistics on this. It is not clear to be that this is necessarily small, nor that 32 is the right number.

57 ↗

(On Diff #26590)

Remove commented-out code.

82 ↗

(On Diff #26590)

This function seems to be doing exactly what PointerMayBeCaptured does (see lib/Analysis/CaptureTracking.cpp), can you use that instead?

103 ↗

(On Diff #26590)

Unguarded recursion should be avoided. Add a depth limit or use a worklist.

105 ↗

(On Diff #26590)

You probably want to filter out comparisons with null, which also don't really capture the address.

138 ↗

(On Diff #26590)

This seems unnecessarily limiting. Why not use GetUnderlyingObjects, and just make sure the condition is satisfied for all underlying pointers?

lib/Transforms/IPO/PassManagerBuilder.cpp

202

Should this be part of the preceeding function?

275

Remove commented-out code.

[majnemer]

lib/Analysis/IPA/StaticGlobalsAA.cpp

123 ↗

(On Diff #26590)

How can GV be a Function?

124 ↗

(On Diff #26590)

What if the local global variable has an external alias?

[samparker]

In D10059#179482, @hfinkel wrote:

The compile-time numbers look good (in the sense that there is no significant difference between the even- and odd-numbered runs).

Please comment on exactly what makes this lighter weight than GlobalsModRef AA, and why this should be a separate pass.

Hi Hal,

GlobalsModRef AA analyses all global values with no limit on the depth of the search, whereas this pass only analyses static variables and obeys the search threshold defined in CaptureTracking. In addition, GlobalsModRef also checks for indirect access to global memory and analyses the call graph. I originally implemented this logic in BasicAA to fill a gap in its understanding of global variables, however I was informed that BasicAA is designed to be stateless, so this pass has been created to maintain the state of the module.

Cheers,
sam

lib/Analysis/IPA/StaticGlobalsAA.cpp

82 ↗

(On Diff #26590)

Looks like it, it also is recursive with a worklist and a threshold

123 ↗

(On Diff #26590)

Ah, good point, I just looked at the inheritance diagram and not properly at the API.

124 ↗

(On Diff #26590)

would it sufficient to additionally check if !isa<GlobalAlias>?

lib/Transforms/IPO/PassManagerBuilder.cpp

202

I tried that, but it caused LLVM to crash. I believe its because that function is also called by populateFunctionPassManager function.

[hfinkel]

It looks like you just uploaded a diff against the previous patch. Please upload the full diff against trunk instead (with full context).

lib/Transforms/IPO/PassManagerBuilder.cpp

202

Okay; please add a comment noting that.

[samparker]

I have rewritten the pass as an Immutable pass, as the module pass seemed to get invalidated and hardly ever used. This does mean that it has to perform the analysis fully every time it is queried, and this increases compilation time of LNT by ~1.1%. It now uses the CaptureTracking system already provided in the LLVM code base.

[samparker]

Hal,

Would you be able to be my reviewer?

Cheers,
sam

[hfinkel]

Hi Sam,

Yes, I'll look at this sometime over the next couple of days.

-Hal

• Original Message -----

From: "Sam Parker" <[e-mail]>
To: "sam parker" <[e-mail]>
Cc: "david majnemer" <[e-mail]>, [e-mail], [e-mail]
Sent: Monday, June 15, 2015 8:08:47 AM
Subject: Re: [PATCH] New alias analysis for static global variables

Hal,

Would you be able to be my reviewer?

Cheers,
sam

http://reviews.llvm.org/D10059

EMAIL PREFERENCES

http://reviews.llvm.org/settings/panel/emailpreferences/

[hfinkel]

In D10059#186158, @samparker wrote:

I have rewritten the pass as an Immutable pass, as the module pass seemed to get invalidated and hardly ever used. This does mean that it has to perform the analysis fully every time it is queried, and this increases compilation time of LNT by ~1.1%. It now uses the CaptureTracking system already provided in the LLVM code base.

It seems sad that you really can't cache the results. You could mark all of the transformations are preserving the analysis. Do we have any transformations that would capture the address of a global where it had not been captured before?

lib/Analysis/StaticGlobalsAA.cpp

146

I'd like to see these calls to GetUnderlyingObjects, and then you can check "all" of the underlying objects to see if all underlying objects in one of the sets are derived from non-addr-taken globals.

[samparker]

Hi Hal,

From the documentation it seems that it doesn't matter if the transformation passes state that they are preserving the analysis or not. I'm not sure about which transformation would affect it except where values are removed or renamed in the global optimiser and GVN.

[hfinkel]

In D10059#196272, @samparker wrote:

Hi Hal,

From the documentation it seems that it doesn't matter if the transformation passes state that they are preserving the analysis or not.

Which documentation?

I'm not sure about which transformation would affect it except where values are removed or renamed in the global optimiser and GVN.

[samparker]

http://llvm.org/docs/AliasAnalysis.html#limitations

[hfinkel]

In D10059#197018, @samparker wrote:

http://llvm.org/docs/AliasAnalysis.html#limitations

That's a bit misleading. You can preserve underlying AA passes (although not the AliasAnalysis analysis group itself). The problems is that if *any* pass does not preserve it, it will be invalidated, and nothing will cause it to be regenerated (unless it is inserted again specifically in the pass manager).

The question here is: Do we have *any* passes in-tree that would not preserve the cache trivially?

[samparker]

In D10059#197376, @hfinkel wrote:

In D10059#197018, @samparker wrote:

http://llvm.org/docs/AliasAnalysis.html#limitations

That's a bit misleading. You can preserve underlying AA passes (although not the AliasAnalysis analysis group itself). The problems is that if *any* pass does not preserve it, it will be invalidated, and nothing will cause it to be regenerated (unless it is inserted again specifically in the pass manager).

The question here is: Do we have *any* passes in-tree that would not preserve the cache trivially?

I'm not sure I follow. The immutable AA passes have no state so how are they invalidated, or does being an ImmutablePass mean that they always run? The previous patch used a ModulePass that created a cache, but was not actually queried unless run directly before some of the transformations, so how would you propose querying the cache once its created?

[hfinkel]

In D10059#197850, @samparker wrote:

In D10059#197376, @hfinkel wrote:

In D10059#197018, @samparker wrote:

http://llvm.org/docs/AliasAnalysis.html#limitations

That's a bit misleading. You can preserve underlying AA passes (although not the AliasAnalysis analysis group itself). The problems is that if *any* pass does not preserve it, it will be invalidated, and nothing will cause it to be regenerated (unless it is inserted again specifically in the pass manager).

The question here is: Do we have *any* passes in-tree that would not preserve the cache trivially?

I'm not sure I follow. The immutable AA passes have no state so how are they invalidated, or does being an ImmutablePass mean that they always run?

An immutable pass is never invalidated and always available.

The previous patch used a ModulePass that created a cache, but was not actually queried unless run directly before some of the transformations, so how would you propose querying the cache once its created?

The reason it is only available when run directly before a transformation is because no transformation preserved the analysis, so it was always invalidated. If all transformations were marked as preserving the analysis then it would stick around.

[samparker]

In D10059#198221, @hfinkel wrote:

In D10059#197850, @samparker wrote:

In D10059#197376, @hfinkel wrote:

In D10059#197018, @samparker wrote:

http://llvm.org/docs/AliasAnalysis.html#limitations

That's a bit misleading. You can preserve underlying AA passes (although not the AliasAnalysis analysis group itself). The problems is that if *any* pass does not preserve it, it will be invalidated, and nothing will cause it to be regenerated (unless it is inserted again specifically in the pass manager).

The question here is: Do we have *any* passes in-tree that would not preserve the cache trivially?

I'm not sure I follow. The immutable AA passes have no state so how are they invalidated, or does being an ImmutablePass mean that they always run?

An immutable pass is never invalidated and always available.

The previous patch used a ModulePass that created a cache, but was not actually queried unless run directly before some of the transformations, so how would you propose querying the cache once its created?

The reason it is only available when run directly before a transformation is because no transformation preserved the analysis, so it was always invalidated. If all transformations were marked as preserving the analysis then it would stick around.

ok, thanks for the clarification. Would it be sensible to only mark the pass as preserved for the passes that already state they preserve the AliasAnalysis group? Then run the pass before these passes? Would this be accepted, it seems quite a departure from the current method?

[hfinkel]

In D10059#198472, @samparker wrote:

In D10059#198221, @hfinkel wrote:

In D10059#197850, @samparker wrote:

In D10059#197376, @hfinkel wrote:

In D10059#197018, @samparker wrote:

http://llvm.org/docs/AliasAnalysis.html#limitations

That's a bit misleading. You can preserve underlying AA passes (although not the AliasAnalysis analysis group itself). The problems is that if *any* pass does not preserve it, it will be invalidated, and nothing will cause it to be regenerated (unless it is inserted again specifically in the pass manager).

The question here is: Do we have *any* passes in-tree that would not preserve the cache trivially?

I'm not sure I follow. The immutable AA passes have no state so how are they invalidated, or does being an ImmutablePass mean that they always run?

An immutable pass is never invalidated and always available.

The previous patch used a ModulePass that created a cache, but was not actually queried unless run directly before some of the transformations, so how would you propose querying the cache once its created?

The reason it is only available when run directly before a transformation is because no transformation preserved the analysis, so it was always invalidated. If all transformations were marked as preserving the analysis then it would stick around.

ok, thanks for the clarification. Would it be sensible to only mark the pass as preserved for the passes that already state they preserve the AliasAnalysis group? Then run the pass before these passes? Would this be accepted, it seems quite a departure from the current method?

No, I think we'd need to mark all passes, and just have it run once. But I don't think we have any passes that would not preserve this particular analysis, do we? They'd need to take the address of a global variable such that the address might no longer appear derived from the original global symbol. This is certainly possible to do, but I can't think of any transformation that would actually do this currently.

[samparker]

In D10059#198488, @hfinkel wrote:

In D10059#198472, @samparker wrote:

In D10059#198221, @hfinkel wrote:

In D10059#197850, @samparker wrote:

In D10059#197376, @hfinkel wrote:

In D10059#197018, @samparker wrote:

http://llvm.org/docs/AliasAnalysis.html#limitations

That's a bit misleading. You can preserve underlying AA passes (although not the AliasAnalysis analysis group itself). The problems is that if *any* pass does not preserve it, it will be invalidated, and nothing will cause it to be regenerated (unless it is inserted again specifically in the pass manager).

The question here is: Do we have *any* passes in-tree that would not preserve the cache trivially?

I'm not sure I follow. The immutable AA passes have no state so how are they invalidated, or does being an ImmutablePass mean that they always run?

An immutable pass is never invalidated and always available.

The previous patch used a ModulePass that created a cache, but was not actually queried unless run directly before some of the transformations, so how would you propose querying the cache once its created?

The reason it is only available when run directly before a transformation is because no transformation preserved the analysis, so it was always invalidated. If all transformations were marked as preserving the analysis then it would stick around.

ok, thanks for the clarification. Would it be sensible to only mark the pass as preserved for the passes that already state they preserve the AliasAnalysis group? Then run the pass before these passes? Would this be accepted, it seems quite a departure from the current method?

No, I think we'd need to mark all passes, and just have it run once. But I don't think we have any passes that would not preserve this particular analysis, do we? They'd need to take the address of a global variable such that the address might no longer appear derived from the original global symbol. This is certainly possible to do, but I can't think of any transformation that would actually do this currently.

Ok. I think the only problem is when global variables get split or renamed.

[hfinkel]

In D10059#199160, @samparker wrote:

In D10059#198488, @hfinkel wrote:

In D10059#198472, @samparker wrote:

In D10059#198221, @hfinkel wrote:

In D10059#197850, @samparker wrote:

In D10059#197376, @hfinkel wrote:

In D10059#197018, @samparker wrote:

http://llvm.org/docs/AliasAnalysis.html#limitations

That's a bit misleading. You can preserve underlying AA passes (although not the AliasAnalysis analysis group itself). The problems is that if *any* pass does not preserve it, it will be invalidated, and nothing will cause it to be regenerated (unless it is inserted again specifically in the pass manager).

The question here is: Do we have *any* passes in-tree that would not preserve the cache trivially?

I'm not sure I follow. The immutable AA passes have no state so how are they invalidated, or does being an ImmutablePass mean that they always run?

An immutable pass is never invalidated and always available.

The previous patch used a ModulePass that created a cache, but was not actually queried unless run directly before some of the transformations, so how would you propose querying the cache once its created?

The reason it is only available when run directly before a transformation is because no transformation preserved the analysis, so it was always invalidated. If all transformations were marked as preserving the analysis then it would stick around.

ok, thanks for the clarification. Would it be sensible to only mark the pass as preserved for the passes that already state they preserve the AliasAnalysis group? Then run the pass before these passes? Would this be accepted, it seems quite a departure from the current method?

No, I think we'd need to mark all passes, and just have it run once. But I don't think we have any passes that would not preserve this particular analysis, do we? They'd need to take the address of a global variable such that the address might no longer appear derived from the original global symbol. This is certainly possible to do, but I can't think of any transformation that would actually do this currently.

Ok. I think the only problem is when global variables get split or renamed.

Can you be more specific. Since we have a conservative fallback for unknown globals, why are these a problem?

[samparker]

In D10059#200100, @hfinkel wrote:

In D10059#199160, @samparker wrote:

In D10059#198488, @hfinkel wrote:

In D10059#198472, @samparker wrote:

In D10059#198221, @hfinkel wrote:

In D10059#197850, @samparker wrote:

In D10059#197376, @hfinkel wrote:

In D10059#197018, @samparker wrote:

http://llvm.org/docs/AliasAnalysis.html#limitations

That's a bit misleading. You can preserve underlying AA passes (although not the AliasAnalysis analysis group itself). The problems is that if *any* pass does not preserve it, it will be invalidated, and nothing will cause it to be regenerated (unless it is inserted again specifically in the pass manager).

The question here is: Do we have *any* passes in-tree that would not preserve the cache trivially?

I'm not sure I follow. The immutable AA passes have no state so how are they invalidated, or does being an ImmutablePass mean that they always run?

An immutable pass is never invalidated and always available.

The previous patch used a ModulePass that created a cache, but was not actually queried unless run directly before some of the transformations, so how would you propose querying the cache once its created?

The reason it is only available when run directly before a transformation is because no transformation preserved the analysis, so it was always invalidated. If all transformations were marked as preserving the analysis then it would stick around.

ok, thanks for the clarification. Would it be sensible to only mark the pass as preserved for the passes that already state they preserve the AliasAnalysis group? Then run the pass before these passes? Would this be accepted, it seems quite a departure from the current method?

No, I think we'd need to mark all passes, and just have it run once. But I don't think we have any passes that would not preserve this particular analysis, do we? They'd need to take the address of a global variable such that the address might no longer appear derived from the original global symbol. This is certainly possible to do, but I can't think of any transformation that would actually do this currently.

Ok. I think the only problem is when global variables get split or renamed.

Can you be more specific. Since we have a conservative fallback for unknown globals, why are these a problem?

Sorry, problem is probably the wrong word, the analysis pass just won't be as effective if it isn't updated when new global values are introduced.

[hfinkel]

In D10059#200254, @samparker wrote:

In D10059#200100, @hfinkel wrote:

In D10059#199160, @samparker wrote:

In D10059#198488, @hfinkel wrote:

In D10059#198472, @samparker wrote:

In D10059#198221, @hfinkel wrote:

In D10059#197850, @samparker wrote:

In D10059#197376, @hfinkel wrote:

In D10059#197018, @samparker wrote:

http://llvm.org/docs/AliasAnalysis.html#limitations

That's a bit misleading. You can preserve underlying AA passes (although not the AliasAnalysis analysis group itself). The problems is that if *any* pass does not preserve it, it will be invalidated, and nothing will cause it to be regenerated (unless it is inserted again specifically in the pass manager).

The question here is: Do we have *any* passes in-tree that would not preserve the cache trivially?

I'm not sure I follow. The immutable AA passes have no state so how are they invalidated, or does being an ImmutablePass mean that they always run?

An immutable pass is never invalidated and always available.

The previous patch used a ModulePass that created a cache, but was not actually queried unless run directly before some of the transformations, so how would you propose querying the cache once its created?

The reason it is only available when run directly before a transformation is because no transformation preserved the analysis, so it was always invalidated. If all transformations were marked as preserving the analysis then it would stick around.

ok, thanks for the clarification. Would it be sensible to only mark the pass as preserved for the passes that already state they preserve the AliasAnalysis group? Then run the pass before these passes? Would this be accepted, it seems quite a departure from the current method?

No, I think we'd need to mark all passes, and just have it run once. But I don't think we have any passes that would not preserve this particular analysis, do we? They'd need to take the address of a global variable such that the address might no longer appear derived from the original global symbol. This is certainly possible to do, but I can't think of any transformation that would actually do this currently.

Ok. I think the only problem is when global variables get split or renamed.

Can you be more specific. Since we have a conservative fallback for unknown globals, why are these a problem?

Sorry, problem is probably the wrong word, the analysis pass just won't be as effective if it isn't updated when new global values are introduced.

Agreed; but I'm not sure we have passes that really do that. Do we?

[hfinkel]

Chandler,

Can you lend an opinion here on how we can/should fit this into the pass manager infrastructure? I'd like to be able to have caching here so that we can do the right thing and also not see a compile-time hit.

Thanks!

[chandlerc]

FWIW, this is just a minor part of GlobalsModRef factored out.

I think that if we want something like this, we should break apart GlobalsModRef rather than duplicating its code here and fixing relatively minor aspects of it.

However, this pattern has all of the problems that GlobalsModRef has (see my recent llvmdev mails). I don't think there is any way to make it sound and reasonable.

Sam, your approach works, but violates the fundamental contract when queried by function passes -- it examines the state of other functions. It also has significant compile time costs than I'm not sure we really should be imposing on LLVM.

I think the right way to get this kind of stuff into LLVM is:

1. Get the pass manager into decent shape
2. Add a constraint about function passes not invalidating some conservative analysis of how globals are escaped and/or captured.
3. Use the above constraint for IP analysis and a conservative and sound local analysis (either forwards like capture tracking or backwards like GetUnderlyingObject) which definitively identifies when one of the memory locations in an alias query comes from outside the function (and thus an escaped memory location).

I'm not even sure we want this, as it sounds expensive and brittle... but it would at least be reasonable relative to the current examples of GlobalsModRef or this pass...

include/llvm/Analysis/Passes.h

namespace llvm {
   class FunctionPass;
   class ImmutablePass;
   class LoopPass;
   class ModulePass;
   class Pass;
   class PassInfo;
   class LibCallInfo;
 
   //===--------------------------------------------------------------------===//
   //
+  // createStaticGlobalAAPass - This pass provides alias info for
+  // static global values that do not have their addresses taken.
+  //
+  ImmutablePass *createStaticGlobalAliasAnalysisPass();
+
+  //===--------------------------------------------------------------------===//
+  //
   // createGlobalsModRefPass - This pass provides alias and mod/ref info for
   // global values that do not have their addresses taken.
   //
   Pass *createGlobalsModRefPass();
 
   //===--------------------------------------------------------------------===//
   //
   // createAliasDebugger - This pass helps debug clients of AA

include/llvm/InitializePasses.h

 void initializeSinkingPass(PassRegistry&);
 void initializeSeparateConstOffsetFromGEPPass(PassRegistry &);
 void initializeSlotIndexesPass(PassRegistry&);
 void initializeSpillPlacementPass(PassRegistry&);
 void initializeSpeculativeExecutionPass(PassRegistry&);
 void initializeStackProtectorPass(PassRegistry&);
 void initializeStackColoringPass(PassRegistry&);
 void initializeStackSlotColoringPass(PassRegistry&);
+void initializeStaticGlobalAliasAnalysisPass(PassRegistry&);
 void initializeStraightLineStrengthReducePass(PassRegistry &);
 void initializeStripDeadDebugInfoPass(PassRegistry&);
 void initializeStripDeadPrototypesPassPass(PassRegistry&);
 void initializeStripDebugDeclarePass(PassRegistry&);
 void initializeStripNonDebugSymbolsPass(PassRegistry&);
 void initializeStripSymbolsPass(PassRegistry&);
 void initializeTailCallElimPass(PassRegistry&);
 void initializeTailDuplicatePassPass(PassRegistry&);

include/llvm/LinkAllPasses.h

       (void) llvm::createRegionInfoPass();
       (void) llvm::createRegionOnlyPrinterPass();
       (void) llvm::createRegionOnlyViewerPass();
       (void) llvm::createRegionPrinterPass();
       (void) llvm::createRegionViewerPass();
       (void) llvm::createSCCPPass();
       (void) llvm::createScalarReplAggregatesPass();
       (void) llvm::createSingleLoopExtractorPass();
+      (void) llvm::createStaticGlobalAliasAnalysisPass();
       (void) llvm::createStripSymbolsPass();
       (void) llvm::createStripNonDebugSymbolsPass();
       (void) llvm::createStripDeadDebugInfoPass();
       (void) llvm::createStripDeadPrototypesPass();
       (void) llvm::createTailCallEliminationPass();
       (void) llvm::createJumpThreadingPass();
       (void) llvm::createUnifyFunctionExitNodesPass();
       (void) llvm::createInstCountPass();

lib/Analysis/Analysis.cpp

void llvm::initializeAnalysis(PassRegistry &Registry) {
   initializeRegionPrinterPass(Registry);
   initializeRegionOnlyViewerPass(Registry);
   initializeRegionOnlyPrinterPass(Registry);
   initializeScalarEvolutionPass(Registry);
   initializeScalarEvolutionAliasAnalysisPass(Registry);
   initializeTargetTransformInfoWrapperPassPass(Registry);
   initializeTypeBasedAliasAnalysisPass(Registry);
   initializeScopedNoAliasAAPass(Registry);
+  initializeStaticGlobalAliasAnalysisPass(Registry);
 }
 
 void LLVMInitializeAnalysis(LLVMPassRegistryRef R) {
   initializeAnalysis(*unwrap(R));
 }
 
 LLVMBool LLVMVerifyModule(LLVMModuleRef M, LLVMVerifierFailureAction Action,
                           char **OutMessages) {

lib/Analysis/CMakeLists.txt

add_llvm_library(LLVMAnalysis
   ScalarEvolutionExpander.cpp
   ScalarEvolutionNormalization.cpp
   SparsePropagation.cpp
   TargetLibraryInfo.cpp
   TargetTransformInfo.cpp
   Trace.cpp
   TypeBasedAliasAnalysis.cpp
   ScopedNoAliasAA.cpp
+  StaticGlobalsAA.cpp
   ValueTracking.cpp
 
   ADDITIONAL_HEADER_DIRS
   ${LLVM_MAIN_INCLUDE_DIR}/llvm/Analysis
   )
 
 add_dependencies(LLVMAnalysis intrinsics_gen)
 
 add_subdirectory(IPA)

lib/Analysis/StaticGlobalsAA.cpp

+//===- StaticGlobalsAA.cpp - Simple Alias Analysis for Static Globals -----===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Analysis/Passes.h"
+#include "llvm/Analysis/AliasAnalysis.h"
+#include "llvm/Analysis/CaptureTracking.h"
+#include "llvm/Analysis/MemoryBuiltins.h"
+#include "llvm/Analysis/ValueTracking.h"
+#include "llvm/IR/Constants.h"
+#include "llvm/IR/DerivedTypes.h"
+#include "llvm/IR/InstIterator.h"
+#include "llvm/IR/Instructions.h"
+#include "llvm/IR/Module.h"
+#include "llvm/Pass.h"
+#include "llvm/Support/Debug.h"
+using namespace llvm;
+
+#define DEBUG_TYPE "staticglobal-aa"
+
+namespace {
+
+  // This global tracker knows that global values are being checked for,
+  // whereas the CaptureTracker APIs are not setup to handle global values.
+  // This means the tracker needs to check whether it the User is an
+  // Instruction. If it is not, its probably a ConstantExpr which includes
+  // GEPs that use GlobalValues; in this case we can check here whether a GEP
+  // is being stored and thus escaping the global.
+  struct GlobalCaptureTracker : public CaptureTracker {
+    explicit GlobalCaptureTracker() : Captured(false) {}
+
+    void tooManyUses() override { Captured = true; }
+
+    bool shouldExplore(const Use *U) override {
+      if (isa<Instruction>(U->getUser()))
+        return true;
+      else if (auto *CE = dyn_cast<ConstantExpr>(U->getUser())) {
+        for (const auto &CEUser : CE->users()) {
+          if (auto *Store = dyn_cast<StoreInst>(CEUser)) {
+            if (Store->getOperand(0) == CE) {
+              Captured = true;
+              break;
+            }
+          }
+        }
+      }
+      return false;
+    }
+
+    bool captured(const Use *U) override {
+      Captured = true;
+      return true;
+    }
+
+    bool Captured;
+  };
+
+  class StaticGlobalAliasAnalysis : public ImmutablePass, public AliasAnalysis {
+
+    SmallPtrSet<const GlobalValue*, 32> NonAddressTakenGlobals;
+
+    Module *M;
+
+    void AnalyzeGlobals();
+
+  public:
+    static char ID;
+    StaticGlobalAliasAnalysis() : ImmutablePass(ID) {
+      initializeStaticGlobalAliasAnalysisPass(*PassRegistry::getPassRegistry());
+    }
+
+    bool doInitialization(Module &M) override {
+      InitializeAliasAnalysis(this, &M.getDataLayout());
+      this->M = &M;
+      return true;
+    }
+
+    void getAnalysisUsage(AnalysisUsage &AU) const override {
+      AliasAnalysis::getAnalysisUsage(AU);
+      AU.setPreservesAll();
+    }
+
+    AliasResult alias(const Location &LocA, const Location &LocB) override;
+
+    /// getAdjustedAnalysisPointer - This method is used when a pass implements
+    /// an analysis interface through multiple inheritance.  If needed, it
+    /// should override this to adjust the this pointer as needed for the
+    /// specified pass info.
+    void *getAdjustedAnalysisPointer(AnalysisID ID) override {
+      if (ID == &AliasAnalysis::ID)
+        return (AliasAnalysis*)this;
+      return this;
+    }
+  };
+} // end anonymous namespace
+
+char StaticGlobalAliasAnalysis::ID = 0;
+INITIALIZE_AG_PASS(StaticGlobalAliasAnalysis, AliasAnalysis,
+                "staticglobal-aa", "Simple Alias Analysis Of Static Globals",
+                false, true, false)
+
+ImmutablePass *llvm::createStaticGlobalAliasAnalysisPass() {
+  return new StaticGlobalAliasAnalysis();
+}
+
+/// AnalyzeGlobals - Scan through the users of all of the internal
+/// GlobalValue's in the Module, recording the one's which do not have their
+/// address taken.
+void StaticGlobalAliasAnalysis::AnalyzeGlobals() {
+  DEBUG(dbgs() << "\nSGAA: Analyzing globals\n");
+  NonAddressTakenGlobals.clear();
+  for (auto &GV : M->globals()) {
+    if (GV.hasLocalLinkage() && !isa<GlobalAlias>(GV)) {
+      // Read-only static, doesn't matter as read-only memory should be picked
+      // up way earlier.
+      if (GV.isConstant()) {
+        continue;
+      }
+      DEBUG(dbgs() << "\nSGAA: Analyze " << GV.getName() << "\n");
+
+      GlobalCaptureTracker Tracker;
+      PointerMayBeCaptured(&GV, &Tracker);
+
+      if (!Tracker.Captured)
+        NonAddressTakenGlobals.insert(&GV);
+    }
+  }
+}
+
+/// alias - If one of the pointers is to a global that we are tracking, and the
+/// other is some random pointer, we know there cannot be an alias, because the
+/// address of the global isn't taken.
+AliasAnalysis::AliasResult
+StaticGlobalAliasAnalysis::alias(const Location &LocA,
+                                 const Location &LocB) {
+  DEBUG(dbgs() << "SGAA: alias\n");
+  AnalyzeGlobals();
+
+  if (!NonAddressTakenGlobals.empty()) {
+    // Get the base object these pointers point to.
+    const Value *UV1 = GetUnderlyingObject(LocA.Ptr, *DL);
+    const Value *UV2 = GetUnderlyingObject(LocB.Ptr, *DL);
+
+
+    // If either of the underlying values is a global, they may be
+    // non-addr-taken globals, which we can answer queries about.
+    const GlobalValue *GV1 = dyn_cast<GlobalValue>(UV1);
+    const GlobalValue *GV2 = dyn_cast<GlobalValue>(UV2);
+    if (GV1 || GV2) {
+      // If the two pointers are derived from two different non-addr-taken
+      // globals, or if one is and the other isn't, we know these can't alias.
+      if (NonAddressTakenGlobals.count(GV1) ||
+          NonAddressTakenGlobals.count(GV2))
+        return NoAlias;
+    }
+  }
+  return AliasAnalysis::alias(LocA, LocB);
+}

lib/CodeGen/Passes.cpp

 // Experimental option to run live interval analysis early.
 static cl::opt<bool> EarlyLiveIntervals("early-live-intervals", cl::Hidden,
     cl::desc("Run live interval analysis earlier in the pipeline"));
 
 static cl::opt<bool> UseCFLAA("use-cfl-aa-in-codegen",
   cl::init(false), cl::Hidden,
   cl::desc("Enable the new, experimental CFL alias analysis in CodeGen"));
 
+static cl::opt<bool>
+UseSGAA("use-staticglobal-aa-in-codegen",
+        cl::init(false), cl::Hidden,
+        cl::desc("Enable alias analysis of static globals in CodeGen"));
+
+
 /// Allow standard passes to be disabled by command line options. This supports
 /// simple binary flags that either suppress the pass or do nothing.
 /// i.e. -disable-mypass=false has no effect.
 /// These should be converted to boolOrDefault in order to use applyOverride.
 static IdentifyingPassPtr applyDisable(IdentifyingPassPtr PassID,
                                        bool Override) {
   if (Override)
     return IdentifyingPassPtr();

 
 /// Add common target configurable passes that perform LLVM IR to IR transforms
 /// following machine independent optimization.
 void TargetPassConfig::addIRPasses() {
   // Basic AliasAnalysis support.
   // Add TypeBasedAliasAnalysis before BasicAliasAnalysis so that
   // BasicAliasAnalysis wins if they disagree. This is intended to help
   // support "obvious" type-punning idioms.
+  if (UseSGAA)
+    addPass(createStaticGlobalAliasAnalysisPass());
   if (UseCFLAA)
     addPass(createCFLAliasAnalysisPass());
   addPass(createTypeBasedAliasAnalysisPass());
   addPass(createScopedNoAliasAAPass());
   addPass(createBasicAliasAnalysisPass());
 
   // Before running any passes, run the verifier to determine if the input
   // coming from the front-end and/or optimizer is valid.

lib/Transforms/IPO/PassManagerBuilder.cpp

RunSLPAfterLoopVectorization("run-slp-after-loop-vectorization",
   cl::desc("Run the SLP vectorizer (and BB vectorizer) after the Loop "
            "vectorizer instead of before"));
 
 static cl::opt<bool> UseCFLAA("use-cfl-aa",
   cl::init(false), cl::Hidden,
   cl::desc("Enable the new, experimental CFL alias analysis"));
 
 static cl::opt<bool>
+UseSGAA("use-staticglobal-aa",
+        cl::init(false), cl::Hidden,
+        cl::desc("Enable alias analysis of static global variables."));
+
+static cl::opt<bool>
 EnableMLSM("mlsm", cl::init(true), cl::Hidden,
            cl::desc("Enable motion of merged load and store"));
 
 static cl::opt<bool> EnableLoopInterchange(
     "enable-loopinterchange", cl::init(false), cl::Hidden,
     cl::desc("Enable the new, experimental LoopInterchange Pass"));
 
 static cl::opt<bool> EnableLoopDistribute(
if (MergeFunctions)
       MPM.add(createMergeFunctionsPass());
     else if (!GlobalExtensions->empty() || !Extensions.empty())
       MPM.add(createBarrierNoopPass());
 
     addExtensionsToPM(EP_EnabledOnOptLevel0, MPM);
     return;
   }
 
   // Add LibraryInfo if we have some.
   if (LibraryInfo)
     MPM.add(new TargetLibraryInfoWrapperPass(*LibraryInfo));
 
+  if (UseSGAA)
+    MPM.add(createStaticGlobalAliasAnalysisPass());
   addInitialAliasAnalysisPasses(MPM);
 
   if (!DisableUnitAtATime) {
     addExtensionsToPM(EP_ModuleOptimizerEarly, MPM);
 
     MPM.add(createIPSCCPPass());              // IP SCCP
     MPM.add(createGlobalOptimizerPass());     // Optimize out global vars
 
void PassManagerBuilder::populateModulePassManager(
 
   if (OptLevel > 1) {
     if (EnableMLSM)
       MPM.add(createMergedLoadStoreMotionPass()); // Merge ld/st in diamonds
     MPM.add(createGVNPass(DisableGVNLoadPRE));  // Remove redundancies
   }
   MPM.add(createMemCpyOptPass());             // Remove memcpy / form memset
   MPM.add(createSCCPPass());                  // Constant prop with SCCP
 
   // Delete dead bit computations (instcombine runs after to fold away the dead
   // computations, and then ADCE will run later to exploit any new DCE
   // opportunities that creates).
   MPM.add(createBitTrackingDCEPass());        // Delete dead bit computations
 
   // Run instcombine after redundancy elimination to exploit opportunities
   // opened up by them.
   MPM.add(createInstructionCombiningPass());

lib/Transforms/Scalar/Scalar.cpp

void llvm::initializeScalarOpts(PassRegistry &Registry) {
   initializeSeparateConstOffsetFromGEPPass(Registry);
   initializeSpeculativeExecutionPass(Registry);
   initializeStraightLineStrengthReducePass(Registry);
   initializeLoadCombinePass(Registry);
   initializePlaceBackedgeSafepointsImplPass(Registry);
   initializePlaceSafepointsPass(Registry);
   initializeFloat2IntPass(Registry);
   initializeLoopDistributePass(Registry);
+  initializeStaticGlobalAliasAnalysisPass(Registry);
 }
 
 void LLVMInitializeScalarOpts(LLVMPassRegistryRef R) {
   initializeScalarOpts(*unwrap(R));
 }
 
 void LLVMAddAggressiveDCEPass(LLVMPassManagerRef PM) {
   unwrap(PM)->add(createAggressiveDCEPass());

 void LLVMAddEarlyCSEPass(LLVMPassManagerRef PM) {
   unwrap(PM)->add(createEarlyCSEPass());
 }
 
 void LLVMAddTypeBasedAliasAnalysisPass(LLVMPassManagerRef PM) {
   unwrap(PM)->add(createTypeBasedAliasAnalysisPass());
 }
 
+void LLVMAddStaticGlobalAliasAnalysisPass(LLVMPassManagerRef PM) {
+  unwrap(PM)->add(createStaticGlobalAliasAnalysisPass());
+}
+
 void LLVMAddScopedNoAliasAAPass(LLVMPassManagerRef PM) {
   unwrap(PM)->add(createScopedNoAliasAAPass());
 }
 
 void LLVMAddBasicAliasAnalysisPass(LLVMPassManagerRef PM) {
   unwrap(PM)->add(createBasicAliasAnalysisPass());
 }
 
 void LLVMAddLowerExpectIntrinsicPass(LLVMPassManagerRef PM) {
   unwrap(PM)->add(createLowerExpectIntrinsicPass());
 }

test/Analysis/StaticGlobalAA/dead-store.ll

+; RUN: opt < %s -O3 -S -use-staticglobal-aa 2>&1 | FileCheck %s
+
+; ModuleID = 'basic.c'
+target datalayout = "e-m:e-i64:64-i128:128-n32:64-S128"
+target triple = "aarch64"
+
+@a.0 = internal unnamed_addr global i32 0
+
+; CHECK-LABEL: @f(
+; CHECK: load
+; CHECK: load
+; CHECK-NOT: load
+; CHECK: store
+; CHECK: store
+; CHECK-NOT: store
+; CHECK: ret
+
+; Function Attrs: nounwind
+define void @f(i32* nocapture %b) #0 {
+entry:
+  %0 = load i32, i32* @a.0, align 4, !tbaa !1
+  %shl = shl i32 %0, 1
+  store i32 %shl, i32* @a.0, align 4, !tbaa !1
+  %arrayidx = getelementptr inbounds i32, i32* %b, i64 1
+  %1 = load i32, i32* %arrayidx, align 4, !tbaa !1
+  %shl1 = shl i32 %1, 1
+  store i32 %shl1, i32* %arrayidx, align 4, !tbaa !1
+  %2 = load i32, i32* @a.0, align 4, !tbaa !1
+  %add = add nsw i32 %2, 2
+  store i32 %add, i32* @a.0, align 4, !tbaa !1
+  ret void
+}
+
+attributes #0 = { nounwind }
+
+!1 = !{!2, !2, i64 0}
+!2 = !{!"int", !3, i64 0}
+!3 = !{!"omnipotent char", !4, i64 0}
+!4 = !{!"Simple C/C++ TBAA"}

test/Analysis/StaticGlobalAA/vectorize-loop.ll

+; RUN: opt < %s -O3 -S -use-staticglobal-aa 2>&1 | FileCheck %s
+
+target datalayout = "e-m:e-i64:64-i128:128-n32:64-S128"
+target triple = "aarch64"
+
+@a = internal unnamed_addr global [5 x i32] zeroinitializer, align 4
+
+; CHECK-LABEL: @f(
+; CHECK: load <4 x i32>
+; CHECK: load <4 x i32>
+; CHECK-NOT: load <4 x i32>
+; CHECK: store <4 x i32>
+; CHECK: store <4 x i32>
+; CHECK-NOT: store <4 x i32>
+; CHECK: ret
+
+; Function Attrs: nounwind
+define void @f(i32* nocapture %b) #0 {
+entry:
+  br label %for.body
+
+for.cond.cleanup:                                 ; preds = %for.body
+  ret void
+
+for.body:                                         ; preds = %for.body, %entry
+  %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %for.body ]
+  %arrayidx = getelementptr inbounds [5 x i32], [5 x i32]* @a, i64 0, i64 %indvars.iv
+  %0 = load i32, i32* %arrayidx, align 4, !tbaa !1
+  %shl = shl i32 %0, 1
+  store i32 %shl, i32* %arrayidx, align 4, !tbaa !1
+  %arrayidx2 = getelementptr inbounds i32, i32* %b, i64 %indvars.iv
+  %1 = load i32, i32* %arrayidx2, align 4, !tbaa !1
+  %shl3 = shl i32 %1, 1
+  store i32 %shl3, i32* %arrayidx2, align 4, !tbaa !1
+  %2 = load i32, i32* %arrayidx, align 4, !tbaa !1
+  %add = add nsw i32 %2, 2
+  store i32 %add, i32* %arrayidx, align 4, !tbaa !1
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %exitcond = icmp eq i64 %indvars.iv.next, 5
+  br i1 %exitcond, label %for.cond.cleanup, label %for.body
+}
+
+attributes #0 = { nounwind }
+
+!1 = !{!2, !2, i64 0}
+!2 = !{!"int", !3, i64 0}
+!3 = !{!"omnipotent char", !4, i64 0}
+!4 = !{!"Simple C/C++ TBAA"}