Index: include/llvm/Analysis/Passes.h =================================================================== --- include/llvm/Analysis/Passes.h +++ include/llvm/Analysis/Passes.h @@ -24,6 +24,8 @@ class PassInfo; class LibCallInfo; + Pass *createStaticGlobalAAPass(); + //===--------------------------------------------------------------------===// // // createGlobalsModRefPass - This pass provides alias and mod/ref info for Index: include/llvm/InitializePasses.h =================================================================== --- include/llvm/InitializePasses.h +++ include/llvm/InitializePasses.h @@ -260,6 +260,7 @@ void initializeStackProtectorPass(PassRegistry&); void initializeStackColoringPass(PassRegistry&); void initializeStackSlotColoringPass(PassRegistry&); +void initializeStaticGlobalAAPass(PassRegistry&); void initializeStraightLineStrengthReducePass(PassRegistry &); void initializeStripDeadDebugInfoPass(PassRegistry&); void initializeStripDeadPrototypesPassPass(PassRegistry&); Index: lib/Analysis/IPA/CMakeLists.txt =================================================================== --- lib/Analysis/IPA/CMakeLists.txt +++ lib/Analysis/IPA/CMakeLists.txt @@ -5,6 +5,7 @@ GlobalsModRef.cpp IPA.cpp InlineCost.cpp + StaticGlobalsAA.cpp ) add_dependencies(LLVMipa intrinsics_gen) Index: lib/Analysis/IPA/IPA.cpp =================================================================== --- lib/Analysis/IPA/IPA.cpp +++ lib/Analysis/IPA/IPA.cpp @@ -23,6 +23,7 @@ initializeCallGraphPrinterPass(Registry); initializeCallGraphViewerPass(Registry); initializeGlobalsModRefPass(Registry); + initializeStaticGlobalAAPass(Registry); } void LLVMInitializeIPA(LLVMPassRegistryRef R) { Index: lib/Analysis/IPA/StaticGlobalsAA.cpp =================================================================== --- /dev/null +++ lib/Analysis/IPA/StaticGlobalsAA.cpp @@ -0,0 +1,179 @@ +//===- StaticGlobalAA.cpp - Simple Mod/Ref Analysis for 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/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 { + class StaticGlobalAA : public ModulePass, public AliasAnalysis { + + SmallPtrSet NonAddressTakenGlobals; + + public: + static char ID; + StaticGlobalAA() : ModulePass(ID) { + initializeStaticGlobalAAPass(*PassRegistry::getPassRegistry()); + } + + bool runOnModule(Module &M) override { + InitializeAliasAnalysis(this, &M.getDataLayout()); + + // Find non-addr taken static globals. + AnalyzeGlobals(M); + + return false; + } + + void AnalyzeGlobals(Module &M); + + void getAnalysisUsage(AnalysisUsage &AU) const override { + AliasAnalysis::getAnalysisUsage(AU); + AU.setPreservesAll(); // Does not transform code + } + + //------------------------------------------------ + // Implement the AliasAnalysis API + // + AliasResult alias(const Location &LocA, const Location &LocB) override; + void deleteValue(Value *V) override; + //void copyValue(Value *From, Value *To) override; + void addEscapingUse(Use &U) 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 PI) override { + if (PI == &AliasAnalysis::ID) + return (AliasAnalysis*)this; + return this; + } + }; +} // end anonymous namespace + +char StaticGlobalAA::ID = 0; +INITIALIZE_AG_PASS_BEGIN(StaticGlobalAA, AliasAnalysis, + "staticglobal-aa", "Simple analysis for static globals", + false, true, false) +INITIALIZE_AG_PASS_END(StaticGlobalAA, AliasAnalysis, + "staticglobal-aa", "Simple analysis for globals", + false, true, false) + +Pass *llvm::createStaticGlobalAAPass() { return new StaticGlobalAA(); } + +static bool hasAddressTaken(Value *V) { + + if (!V->getType()->isPointerTy()) { + return false; + } + + // Iterate through the users of the value to see if they take the address + // somehow. + for (Use &U : V->uses()) { + User *VU = U.getUser(); + + if (isa(VU)) + continue; + // Using the address to store data, not storing the pointer itself. + else if (isa(VU)) { + if (VU->getOperand(0) != V) + continue; + } + // GEP and BitCast do not take the address, but could be nested within + // instructions that do. + else if (isa(VU) || isa(VU)) { + if (!hasAddressTaken(VU)) + continue; + } + DEBUG(dbgs() << "StaticGlobalAA: " << V->getName() + << " has its address taken\n"); + return true; + } + DEBUG(dbgs() << "StaticGlobalAA: " << V->getName() + << " does not have its address taken\n"); + return false; +} + +/// AnalyzeGlobals - Scan through the users of all of the internal +/// GlobalValue's in the program. If none of them have their "address taken" +/// (really, their address passed to something nontrivial), record this fact, +/// and record the functions that they are used directly in. +void StaticGlobalAA::AnalyzeGlobals(Module &M) { + DEBUG(dbgs() << "StaticGlobalAA: Analyzing globals\n"); + for (auto &GV : M.globals()) { + if (GV.hasLocalLinkage()) { + if (!isa(GV)) + if (!hasAddressTaken(&GV)) + 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 +StaticGlobalAA::alias(const Location &LocA, + const Location &LocB) { + // 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(UV1); + const GlobalValue *GV2 = dyn_cast(UV2); + if (GV1 || GV2) { + // If the global's address is taken, pretend we don't know it's a pointer to + // the global. + if (GV1 && !NonAddressTakenGlobals.count(GV1)) GV1 = nullptr; + if (GV2 && !NonAddressTakenGlobals.count(GV2)) GV2 = nullptr; + + // 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 ((GV1 || GV2) && GV1 != GV2) { + DEBUG(dbgs() << "Found NoAlias with static global\n"); + return NoAlias; + } + + // Otherwise if they are both derived from the same addr-taken global, we + // can't know the two accesses don't overlap. + } + return AliasAnalysis::alias(LocA, LocB); +} + +//===----------------------------------------------------------------------===// +// Methods to update the analysis as a result of the client transformation. +// +void StaticGlobalAA::deleteValue(Value *V) { + if (GlobalValue *GV = dyn_cast(V)) + NonAddressTakenGlobals.erase(GV); + AliasAnalysis::deleteValue(V); +} + +void StaticGlobalAA::addEscapingUse(Use &U) { + if (GlobalValue *GV = dyn_cast(U.get())) { + DEBUG(dbgs() << "EscapingUse added" << GV->getName() << "\n"); + NonAddressTakenGlobals.erase(GV); + } + + AliasAnalysis::addEscapingUse(U); +} Index: lib/Transforms/IPO/PassManagerBuilder.cpp =================================================================== --- lib/Transforms/IPO/PassManagerBuilder.cpp +++ lib/Transforms/IPO/PassManagerBuilder.cpp @@ -199,6 +199,7 @@ MPM.add(new TargetLibraryInfoWrapperPass(*LibraryInfo)); addInitialAliasAnalysisPasses(MPM); + MPM.add(createStaticGlobalAAPass()); if (!DisableUnitAtATime) { addExtensionsToPM(EP_ModuleOptimizerEarly, MPM); @@ -271,6 +272,8 @@ // opportunities that creates). MPM.add(createBitTrackingDCEPass()); // Delete dead bit computations + //MPM.add(createStaticGlobalAAPass()); + // Run instcombine after redundancy elimination to exploit opportunities // opened up by them. MPM.add(createInstructionCombiningPass());