diff options
-rw-r--r-- | include/llvm/Transforms/Utils/GlobalStatus.h | 82 | ||||
-rw-r--r-- | lib/Transforms/IPO/GlobalOpt.cpp | 210 | ||||
-rw-r--r-- | lib/Transforms/IPO/Internalize.cpp | 21 | ||||
-rw-r--r-- | lib/Transforms/Utils/CMakeLists.txt | 1 | ||||
-rw-r--r-- | lib/Transforms/Utils/GlobalStatus.cpp | 178 | ||||
-rw-r--r-- | test/LTO/cfi_endproc.ll | 3 | ||||
-rw-r--r-- | test/Transforms/Internalize/lists.ll | 12 |
7 files changed, 294 insertions, 213 deletions
diff --git a/include/llvm/Transforms/Utils/GlobalStatus.h b/include/llvm/Transforms/Utils/GlobalStatus.h new file mode 100644 index 0000000..c366095 --- /dev/null +++ b/include/llvm/Transforms/Utils/GlobalStatus.h @@ -0,0 +1,82 @@ +//===- GlobalStatus.h - Compute status info for globals ---------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_UTILS_GLOBALSTATUS_H +#define LLVM_TRANSFORMS_UTILS_GLOBALSTATUS_H + +#include "llvm/IR/Instructions.h" + +namespace llvm { +class Value; +class Function; + +/// It is safe to destroy a constant iff it is only used by constants itself. +/// Note that constants cannot be cyclic, so this test is pretty easy to +/// implement recursively. +/// +bool isSafeToDestroyConstant(const Constant *C); + +/// As we analyze each global, keep track of some information about it. If we +/// find out that the address of the global is taken, none of this info will be +/// accurate. +struct GlobalStatus { + /// True if the global's address is used in a comparison. + bool IsCompared; + + /// True if the global is ever loaded. If the global isn't ever loaded it + /// can be deleted. + bool IsLoaded; + + /// Keep track of what stores to the global look like. + enum StoredType { + /// There is no store to this global. It can thus be marked constant. + NotStored, + + /// This global is stored to, but the only thing stored is the constant it + /// was initialized with. This is only tracked for scalar globals. + InitializerStored, + + /// This global is stored to, but only its initializer and one other value + /// is ever stored to it. If this global isStoredOnce, we track the value + /// stored to it in StoredOnceValue below. This is only tracked for scalar + /// globals. + StoredOnce, + + /// This global is stored to by multiple values or something else that we + /// cannot track. + Stored + } StoredType; + + /// If only one value (besides the initializer constant) is ever stored to + /// this global, keep track of what value it is. + Value *StoredOnceValue; + + /// These start out null/false. When the first accessing function is noticed, + /// it is recorded. When a second different accessing function is noticed, + /// HasMultipleAccessingFunctions is set to true. + const Function *AccessingFunction; + bool HasMultipleAccessingFunctions; + + /// Set to true if this global has a user that is not an instruction (e.g. a + /// constant expr or GV initializer). + bool HasNonInstructionUser; + + /// Set to the strongest atomic ordering requirement. + AtomicOrdering Ordering; + + /// Look at all uses of the global and fill in the GlobalStatus structure. If + /// the global has its address taken, return true to indicate we can't do + /// anything with it. + static bool analyzeGlobal(const Value *V, GlobalStatus &GS); + + GlobalStatus(); +}; +} + +#endif diff --git a/lib/Transforms/IPO/GlobalOpt.cpp b/lib/Transforms/IPO/GlobalOpt.cpp index 7b2110f..74ed4e2 100644 --- a/lib/Transforms/IPO/GlobalOpt.cpp +++ b/lib/Transforms/IPO/GlobalOpt.cpp @@ -38,6 +38,7 @@ #include "llvm/Support/MathExtras.h" #include "llvm/Support/raw_ostream.h" #include "llvm/Target/TargetLibraryInfo.h" +#include "llvm/Transforms/Utils/GlobalStatus.h" #include "llvm/Transforms/Utils/ModuleUtils.h" #include <algorithm> using namespace llvm; @@ -60,7 +61,6 @@ STATISTIC(NumAliasesRemoved, "Number of global aliases eliminated"); STATISTIC(NumCXXDtorsRemoved, "Number of global C++ destructors removed"); namespace { - struct GlobalStatus; struct GlobalOpt : public ModulePass { virtual void getAnalysisUsage(AnalysisUsage &AU) const { AU.addRequired<TargetLibraryInfo>(); @@ -99,214 +99,8 @@ ModulePass *llvm::createGlobalOptimizerPass() { return new GlobalOpt(); } namespace { -/// As we analyze each global, keep track of some information about it. If we -/// find out that the address of the global is taken, none of this info will be -/// accurate. -struct GlobalStatus { - /// True if the global's address is used in a comparison. - bool IsCompared; - /// True if the global is ever loaded. If the global isn't ever loaded it can - /// be deleted. - bool IsLoaded; - /// Keep track of what stores to the global look like. - /// - enum StoredType { - /// There is no store to this global. It can thus be marked constant. - NotStored, - - /// This global is stored to, but the only thing stored is the constant it - /// was initialized with. This is only tracked for scalar globals. - InitializerStored, - - /// This global is stored to, but only its initializer and one other value - /// is ever stored to it. If this global StoredOnce, we track the value - /// stored to it in StoredOnceValue below. This is only tracked for scalar - /// globals. - StoredOnce, - - /// This global is stored to by multiple values or something else that we - /// cannot track. - Stored - } StoredType; - - /// StoredOnceValue - If only one value (besides the initializer constant) is - /// ever stored to this global, keep track of what value it is. - Value *StoredOnceValue; - - /// AccessingFunction/HasMultipleAccessingFunctions - These start out - /// null/false. When the first accessing function is noticed, it is recorded. - /// When a second different accessing function is noticed, - /// HasMultipleAccessingFunctions is set to true. - const Function *AccessingFunction; - bool HasMultipleAccessingFunctions; - - /// HasNonInstructionUser - Set to true if this global has a user that is not - /// an instruction (e.g. a constant expr or GV initializer). - bool HasNonInstructionUser; - - /// AtomicOrdering - Set to the strongest atomic ordering requirement. - AtomicOrdering Ordering; - - GlobalStatus() : IsCompared(false), IsLoaded(false), StoredType(NotStored), - StoredOnceValue(0), AccessingFunction(0), - HasMultipleAccessingFunctions(false), - HasNonInstructionUser(false), Ordering(NotAtomic) {} -}; - -} - -/// StrongerOrdering - Return the stronger of the two ordering. If the two -/// orderings are acquire and release, then return AcquireRelease. -/// -static AtomicOrdering StrongerOrdering(AtomicOrdering X, AtomicOrdering Y) { - if (X == Acquire && Y == Release) return AcquireRelease; - if (Y == Acquire && X == Release) return AcquireRelease; - return (AtomicOrdering)std::max(X, Y); -} - -/// It is safe to destroy a constant iff it is only used by constants itself. -/// Note that constants cannot be cyclic, so this test is pretty easy to -/// implement recursively. -/// -static bool isSafeToDestroyConstant(const Constant *C) { - if (isa<GlobalValue>(C)) - return false; - - for (Value::const_use_iterator UI = C->use_begin(), E = C->use_end(); UI != E; - ++UI) - if (const Constant *CU = dyn_cast<Constant>(*UI)) { - if (!isSafeToDestroyConstant(CU)) - return false; - } else - return false; - return true; -} - -static bool analyzeGlobalAux(const Value *V, GlobalStatus &GS, - SmallPtrSet<const PHINode *, 16> &PHIUsers) { - for (Value::const_use_iterator UI = V->use_begin(), E = V->use_end(); UI != E; - ++UI) { - const User *U = *UI; - if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(U)) { - GS.HasNonInstructionUser = true; - - // If the result of the constantexpr isn't pointer type, then we won't - // know to expect it in various places. Just reject early. - if (!isa<PointerType>(CE->getType())) return true; - - if (analyzeGlobalAux(CE, GS, PHIUsers)) - return true; - } else if (const Instruction *I = dyn_cast<Instruction>(U)) { - if (!GS.HasMultipleAccessingFunctions) { - const Function *F = I->getParent()->getParent(); - if (GS.AccessingFunction == 0) - GS.AccessingFunction = F; - else if (GS.AccessingFunction != F) - GS.HasMultipleAccessingFunctions = true; - } - if (const LoadInst *LI = dyn_cast<LoadInst>(I)) { - GS.IsLoaded = true; - // Don't hack on volatile loads. - if (LI->isVolatile()) return true; - GS.Ordering = StrongerOrdering(GS.Ordering, LI->getOrdering()); - } else if (const StoreInst *SI = dyn_cast<StoreInst>(I)) { - // Don't allow a store OF the address, only stores TO the address. - if (SI->getOperand(0) == V) return true; - - // Don't hack on volatile stores. - if (SI->isVolatile()) return true; - - GS.Ordering = StrongerOrdering(GS.Ordering, SI->getOrdering()); - - // If this is a direct store to the global (i.e., the global is a scalar - // value, not an aggregate), keep more specific information about - // stores. - if (GS.StoredType != GlobalStatus::Stored) { - if (const GlobalVariable *GV = dyn_cast<GlobalVariable>( - SI->getOperand(1))) { - Value *StoredVal = SI->getOperand(0); - - if (Constant *C = dyn_cast<Constant>(StoredVal)) { - if (C->isThreadDependent()) { - // The stored value changes between threads; don't track it. - return true; - } - } - - if (StoredVal == GV->getInitializer()) { - if (GS.StoredType < GlobalStatus::InitializerStored) - GS.StoredType = GlobalStatus::InitializerStored; - } else if (isa<LoadInst>(StoredVal) && - cast<LoadInst>(StoredVal)->getOperand(0) == GV) { - if (GS.StoredType < GlobalStatus::InitializerStored) - GS.StoredType = GlobalStatus::InitializerStored; - } else if (GS.StoredType < GlobalStatus::StoredOnce) { - GS.StoredType = GlobalStatus::StoredOnce; - GS.StoredOnceValue = StoredVal; - } else if (GS.StoredType == GlobalStatus::StoredOnce && - GS.StoredOnceValue == StoredVal) { - // noop. - } else { - GS.StoredType = GlobalStatus::Stored; - } - } else { - GS.StoredType = GlobalStatus::Stored; - } - } - } else if (isa<BitCastInst>(I)) { - if (analyzeGlobalAux(I, GS, PHIUsers)) - return true; - } else if (isa<GetElementPtrInst>(I)) { - if (analyzeGlobalAux(I, GS, PHIUsers)) - return true; - } else if (isa<SelectInst>(I)) { - if (analyzeGlobalAux(I, GS, PHIUsers)) - return true; - } else if (const PHINode *PN = dyn_cast<PHINode>(I)) { - // PHI nodes we can check just like select or GEP instructions, but we - // have to be careful about infinite recursion. - if (PHIUsers.insert(PN)) // Not already visited. - if (analyzeGlobalAux(I, GS, PHIUsers)) - return true; - } else if (isa<CmpInst>(I)) { - GS.IsCompared = true; - } else if (const MemTransferInst *MTI = dyn_cast<MemTransferInst>(I)) { - if (MTI->isVolatile()) return true; - if (MTI->getArgOperand(0) == V) - GS.StoredType = GlobalStatus::Stored; - if (MTI->getArgOperand(1) == V) - GS.IsLoaded = true; - } else if (const MemSetInst *MSI = dyn_cast<MemSetInst>(I)) { - assert(MSI->getArgOperand(0) == V && "Memset only takes one pointer!"); - if (MSI->isVolatile()) return true; - GS.StoredType = GlobalStatus::Stored; - } else { - return true; // Any other non-load instruction might take address! - } - } else if (const Constant *C = dyn_cast<Constant>(U)) { - GS.HasNonInstructionUser = true; - // We might have a dead and dangling constant hanging off of here. - if (!isSafeToDestroyConstant(C)) - return true; - } else { - GS.HasNonInstructionUser = true; - // Otherwise must be some other user. - return true; - } - } - - return false; -} - -/// Look at all uses of the global and fill in the GlobalStatus -/// structure. If the global has its address taken, return true to indicate we -/// can't do anything with it. -/// -static bool analyzeGlobal(const Value *V, GlobalStatus &GS) { - SmallPtrSet<const PHINode *, 16> PHIUsers; - return analyzeGlobalAux(V, GS, PHIUsers); } /// isLeakCheckerRoot - Is this global variable possibly used by a leak checker @@ -1927,7 +1721,7 @@ bool GlobalOpt::ProcessGlobal(GlobalVariable *GV, GlobalStatus GS; - if (analyzeGlobal(GV, GS)) + if (GlobalStatus::analyzeGlobal(GV, GS)) return false; if (!GS.IsCompared && !GV->hasUnnamedAddr()) { diff --git a/lib/Transforms/IPO/Internalize.cpp b/lib/Transforms/IPO/Internalize.cpp index f20a7bd..e615918 100644 --- a/lib/Transforms/IPO/Internalize.cpp +++ b/lib/Transforms/IPO/Internalize.cpp @@ -11,6 +11,19 @@ // If the function or variable is not in the list of external names given to // the pass it is marked as internal. // +// This transformation would not be legal or profitable in a regular +// compilation, but it gets extra information from the linker about what is safe +// or profitable. +// +// As an example of a normally illegal transformation: Internalizing a function +// with external linkage. Only if we are told it is only used from within this +// module, it is safe to do it. +// +// On the profitability side: It is always legal to internalize a linkonce_odr +// whose address is not used. Doing so normally would introduce code bloat, but +// if we are told by the linker that the only use of this would be for a +// DSO symbol table, it is profitable to hide it. +// //===----------------------------------------------------------------------===// #define DEBUG_TYPE "internalize" @@ -23,6 +36,7 @@ #include "llvm/Support/CommandLine.h" #include "llvm/Support/Debug.h" #include "llvm/Support/raw_ostream.h" +#include "llvm/Transforms/Utils/GlobalStatus.h" #include "llvm/Transforms/Utils/ModuleUtils.h" #include <fstream> #include <set> @@ -142,8 +156,11 @@ static bool shouldInternalize(const GlobalValue &GV, if (GV.hasUnnamedAddr()) return true; - // FIXME: Check if the address is used. - return false; + GlobalStatus GS; + if (GlobalStatus::analyzeGlobal(&GV, GS)) + return false; + + return !GS.IsCompared; } bool InternalizePass::runOnModule(Module &M) { diff --git a/lib/Transforms/Utils/CMakeLists.txt b/lib/Transforms/Utils/CMakeLists.txt index 3648fd6..5afd6b8 100644 --- a/lib/Transforms/Utils/CMakeLists.txt +++ b/lib/Transforms/Utils/CMakeLists.txt @@ -8,6 +8,7 @@ add_llvm_library(LLVMTransformUtils CmpInstAnalysis.cpp CodeExtractor.cpp DemoteRegToStack.cpp + GlobalStatus.cpp InlineFunction.cpp InstructionNamer.cpp IntegerDivision.cpp diff --git a/lib/Transforms/Utils/GlobalStatus.cpp b/lib/Transforms/Utils/GlobalStatus.cpp new file mode 100644 index 0000000..8fb79aa --- /dev/null +++ b/lib/Transforms/Utils/GlobalStatus.cpp @@ -0,0 +1,178 @@ +//===-- GlobalStatus.cpp - Compute status info 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/ADT/SmallPtrSet.h" +#include "llvm/IR/BasicBlock.h" +#include "llvm/IR/GlobalVariable.h" +#include "llvm/IR/IntrinsicInst.h" +#include "llvm/Transforms/Utils/GlobalStatus.h" + +using namespace llvm; + +/// Return the stronger of the two ordering. If the two orderings are acquire +/// and release, then return AcquireRelease. +/// +static AtomicOrdering strongerOrdering(AtomicOrdering X, AtomicOrdering Y) { + if (X == Acquire && Y == Release) + return AcquireRelease; + if (Y == Acquire && X == Release) + return AcquireRelease; + return (AtomicOrdering)std::max(X, Y); +} + +/// It is safe to destroy a constant iff it is only used by constants itself. +/// Note that constants cannot be cyclic, so this test is pretty easy to +/// implement recursively. +/// +bool llvm::isSafeToDestroyConstant(const Constant *C) { + if (isa<GlobalValue>(C)) + return false; + + for (Value::const_use_iterator UI = C->use_begin(), E = C->use_end(); UI != E; + ++UI) + if (const Constant *CU = dyn_cast<Constant>(*UI)) { + if (!isSafeToDestroyConstant(CU)) + return false; + } else + return false; + return true; +} + +static bool analyzeGlobalAux(const Value *V, GlobalStatus &GS, + SmallPtrSet<const PHINode *, 16> &PhiUsers) { + for (Value::const_use_iterator UI = V->use_begin(), E = V->use_end(); UI != E; + ++UI) { + const User *U = *UI; + if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(U)) { + GS.HasNonInstructionUser = true; + + // If the result of the constantexpr isn't pointer type, then we won't + // know to expect it in various places. Just reject early. + if (!isa<PointerType>(CE->getType())) + return true; + + if (analyzeGlobalAux(CE, GS, PhiUsers)) + return true; + } else if (const Instruction *I = dyn_cast<Instruction>(U)) { + if (!GS.HasMultipleAccessingFunctions) { + const Function *F = I->getParent()->getParent(); + if (GS.AccessingFunction == 0) + GS.AccessingFunction = F; + else if (GS.AccessingFunction != F) + GS.HasMultipleAccessingFunctions = true; + } + if (const LoadInst *LI = dyn_cast<LoadInst>(I)) { + GS.IsLoaded = true; + // Don't hack on volatile loads. + if (LI->isVolatile()) + return true; + GS.Ordering = strongerOrdering(GS.Ordering, LI->getOrdering()); + } else if (const StoreInst *SI = dyn_cast<StoreInst>(I)) { + // Don't allow a store OF the address, only stores TO the address. + if (SI->getOperand(0) == V) + return true; + + // Don't hack on volatile stores. + if (SI->isVolatile()) + return true; + + GS.Ordering = strongerOrdering(GS.Ordering, SI->getOrdering()); + + // If this is a direct store to the global (i.e., the global is a scalar + // value, not an aggregate), keep more specific information about + // stores. + if (GS.StoredType != GlobalStatus::Stored) { + if (const GlobalVariable *GV = + dyn_cast<GlobalVariable>(SI->getOperand(1))) { + Value *StoredVal = SI->getOperand(0); + + if (Constant *C = dyn_cast<Constant>(StoredVal)) { + if (C->isThreadDependent()) { + // The stored value changes between threads; don't track it. + return true; + } + } + + if (StoredVal == GV->getInitializer()) { + if (GS.StoredType < GlobalStatus::InitializerStored) + GS.StoredType = GlobalStatus::InitializerStored; + } else if (isa<LoadInst>(StoredVal) && + cast<LoadInst>(StoredVal)->getOperand(0) == GV) { + if (GS.StoredType < GlobalStatus::InitializerStored) + GS.StoredType = GlobalStatus::InitializerStored; + } else if (GS.StoredType < GlobalStatus::StoredOnce) { + GS.StoredType = GlobalStatus::StoredOnce; + GS.StoredOnceValue = StoredVal; + } else if (GS.StoredType == GlobalStatus::StoredOnce && + GS.StoredOnceValue == StoredVal) { + // noop. + } else { + GS.StoredType = GlobalStatus::Stored; + } + } else { + GS.StoredType = GlobalStatus::Stored; + } + } + } else if (isa<BitCastInst>(I)) { + if (analyzeGlobalAux(I, GS, PhiUsers)) + return true; + } else if (isa<GetElementPtrInst>(I)) { + if (analyzeGlobalAux(I, GS, PhiUsers)) + return true; + } else if (isa<SelectInst>(I)) { + if (analyzeGlobalAux(I, GS, PhiUsers)) + return true; + } else if (const PHINode *PN = dyn_cast<PHINode>(I)) { + // PHI nodes we can check just like select or GEP instructions, but we + // have to be careful about infinite recursion. + if (PhiUsers.insert(PN)) // Not already visited. + if (analyzeGlobalAux(I, GS, PhiUsers)) + return true; + } else if (isa<CmpInst>(I)) { + GS.IsCompared = true; + } else if (const MemTransferInst *MTI = dyn_cast<MemTransferInst>(I)) { + if (MTI->isVolatile()) + return true; + if (MTI->getArgOperand(0) == V) + GS.StoredType = GlobalStatus::Stored; + if (MTI->getArgOperand(1) == V) + GS.IsLoaded = true; + } else if (const MemSetInst *MSI = dyn_cast<MemSetInst>(I)) { + assert(MSI->getArgOperand(0) == V && "Memset only takes one pointer!"); + if (MSI->isVolatile()) + return true; + GS.StoredType = GlobalStatus::Stored; + } else { + return true; // Any other non-load instruction might take address! + } + } else if (const Constant *C = dyn_cast<Constant>(U)) { + GS.HasNonInstructionUser = true; + // We might have a dead and dangling constant hanging off of here. + if (!isSafeToDestroyConstant(C)) + return true; + } else { + GS.HasNonInstructionUser = true; + // Otherwise must be some other user. + return true; + } + } + + return false; +} + +bool GlobalStatus::analyzeGlobal(const Value *V, GlobalStatus &GS) { + SmallPtrSet<const PHINode *, 16> PhiUsers; + return analyzeGlobalAux(V, GS, PhiUsers); +} + +GlobalStatus::GlobalStatus() + : IsCompared(false), IsLoaded(false), StoredType(NotStored), + StoredOnceValue(0), AccessingFunction(0), + HasMultipleAccessingFunctions(false), HasNonInstructionUser(false), + Ordering(NotAtomic) {} diff --git a/test/LTO/cfi_endproc.ll b/test/LTO/cfi_endproc.ll index d8818d2..a5cc649 100644 --- a/test/LTO/cfi_endproc.ll +++ b/test/LTO/cfi_endproc.ll @@ -29,6 +29,9 @@ define i32 @main(i32 %argc, i8** %argv) { ; RUN: llvm-nm %t | FileCheck %s -check-prefix=ZED1_AND_ZED2 ; ZED1_AND_ZED2: V zed1 @zed1 = linkonce_odr global i32 42 +define i32* @get_zed1() { + ret i32* @zed1 +} ; ZED1_AND_ZED2: d zed2 @zed2 = linkonce_odr unnamed_addr global i32 42 diff --git a/test/Transforms/Internalize/lists.ll b/test/Transforms/Internalize/lists.ll index 59fe073..3ebf0ed 100644 --- a/test/Transforms/Internalize/lists.ll +++ b/test/Transforms/Internalize/lists.ll @@ -15,7 +15,7 @@ ; Put zed1 and zed2 in the symbol table. If the address is not relevant, we ; internalize them. -; RUN: opt < %s -internalize -internalize-dso-list zed1,zed2 -S | FileCheck --check-prefix=ZED1_AND_ZED2 %s +; RUN: opt < %s -internalize -internalize-dso-list zed1,zed2,zed3 -S | FileCheck --check-prefix=ZEDS %s ; ALL: @i = internal global ; FOO_AND_J: @i = internal global @@ -29,12 +29,18 @@ ; FOO_J_AND_BAR: @j = global @j = global i32 0 -; ZED1_AND_ZED2: @zed1 = linkonce_odr global i32 42 +; ZEDS: @zed1 = internal global i32 42 @zed1 = linkonce_odr global i32 42 -; ZED1_AND_ZED2: @zed2 = internal unnamed_addr global i32 42 +; ZEDS: @zed2 = internal unnamed_addr global i32 42 @zed2 = linkonce_odr unnamed_addr global i32 42 +; ZEDS: @zed3 = linkonce_odr global i32 42 +@zed3 = linkonce_odr global i32 42 +define i32* @get_zed3() { + ret i32* @zed3 +} + ; ALL: define internal void @main() { ; FOO_AND_J: define internal void @main() { ; FOO_AND_BAR: define internal void @main() { |