1 //===-- GlobalStatus.cpp - Compute status info for globals -----------------==//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 #include "llvm/ADT/SmallPtrSet.h"
11 #include "llvm/IR/BasicBlock.h"
12 #include "llvm/IR/CallSite.h"
13 #include "llvm/IR/Constant.h"
14 #include "llvm/IR/Constants.h"
15 #include "llvm/IR/GlobalValue.h"
16 #include "llvm/IR/GlobalVariable.h"
17 #include "llvm/IR/InstrTypes.h"
18 #include "llvm/IR/Instruction.h"
19 #include "llvm/IR/Instructions.h"
20 #include "llvm/IR/IntrinsicInst.h"
21 #include "llvm/Transforms/Utils/GlobalStatus.h"
22 #include "llvm/IR/Use.h"
23 #include "llvm/IR/User.h"
24 #include "llvm/IR/Value.h"
25 #include "llvm/Support/AtomicOrdering.h"
26 #include "llvm/Support/Casting.h"
32 /// Return the stronger of the two ordering. If the two orderings are acquire
33 /// and release, then return AcquireRelease.
35 static AtomicOrdering strongerOrdering(AtomicOrdering X, AtomicOrdering Y) {
36 if ((X == AtomicOrdering::Acquire && Y == AtomicOrdering::Release) ||
37 (Y == AtomicOrdering::Acquire && X == AtomicOrdering::Release))
38 return AtomicOrdering::AcquireRelease;
39 return (AtomicOrdering)std::max((unsigned)X, (unsigned)Y);
42 /// It is safe to destroy a constant iff it is only used by constants itself.
43 /// Note that constants cannot be cyclic, so this test is pretty easy to
44 /// implement recursively.
46 bool llvm::isSafeToDestroyConstant(const Constant *C) {
47 if (isa<GlobalValue>(C))
50 if (isa<ConstantData>(C))
53 for (const User *U : C->users())
54 if (const Constant *CU = dyn_cast<Constant>(U)) {
55 if (!isSafeToDestroyConstant(CU))
62 static bool analyzeGlobalAux(const Value *V, GlobalStatus &GS,
63 SmallPtrSetImpl<const PHINode *> &PhiUsers) {
64 if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(V))
65 if (GV->isExternallyInitialized())
66 GS.StoredType = GlobalStatus::StoredOnce;
68 for (const Use &U : V->uses()) {
69 const User *UR = U.getUser();
70 if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(UR)) {
71 GS.HasNonInstructionUser = true;
73 // If the result of the constantexpr isn't pointer type, then we won't
74 // know to expect it in various places. Just reject early.
75 if (!isa<PointerType>(CE->getType()))
78 if (analyzeGlobalAux(CE, GS, PhiUsers))
80 } else if (const Instruction *I = dyn_cast<Instruction>(UR)) {
81 if (!GS.HasMultipleAccessingFunctions) {
82 const Function *F = I->getParent()->getParent();
83 if (!GS.AccessingFunction)
84 GS.AccessingFunction = F;
85 else if (GS.AccessingFunction != F)
86 GS.HasMultipleAccessingFunctions = true;
88 if (const LoadInst *LI = dyn_cast<LoadInst>(I)) {
90 // Don't hack on volatile loads.
93 GS.Ordering = strongerOrdering(GS.Ordering, LI->getOrdering());
94 } else if (const StoreInst *SI = dyn_cast<StoreInst>(I)) {
95 // Don't allow a store OF the address, only stores TO the address.
96 if (SI->getOperand(0) == V)
99 // Don't hack on volatile stores.
100 if (SI->isVolatile())
103 GS.Ordering = strongerOrdering(GS.Ordering, SI->getOrdering());
105 // If this is a direct store to the global (i.e., the global is a scalar
106 // value, not an aggregate), keep more specific information about
108 if (GS.StoredType != GlobalStatus::Stored) {
109 if (const GlobalVariable *GV =
110 dyn_cast<GlobalVariable>(SI->getOperand(1))) {
111 Value *StoredVal = SI->getOperand(0);
113 if (Constant *C = dyn_cast<Constant>(StoredVal)) {
114 if (C->isThreadDependent()) {
115 // The stored value changes between threads; don't track it.
120 if (GV->hasInitializer() && StoredVal == GV->getInitializer()) {
121 if (GS.StoredType < GlobalStatus::InitializerStored)
122 GS.StoredType = GlobalStatus::InitializerStored;
123 } else if (isa<LoadInst>(StoredVal) &&
124 cast<LoadInst>(StoredVal)->getOperand(0) == GV) {
125 if (GS.StoredType < GlobalStatus::InitializerStored)
126 GS.StoredType = GlobalStatus::InitializerStored;
127 } else if (GS.StoredType < GlobalStatus::StoredOnce) {
128 GS.StoredType = GlobalStatus::StoredOnce;
129 GS.StoredOnceValue = StoredVal;
130 } else if (GS.StoredType == GlobalStatus::StoredOnce &&
131 GS.StoredOnceValue == StoredVal) {
134 GS.StoredType = GlobalStatus::Stored;
137 GS.StoredType = GlobalStatus::Stored;
140 } else if (isa<BitCastInst>(I)) {
141 if (analyzeGlobalAux(I, GS, PhiUsers))
143 } else if (isa<GetElementPtrInst>(I)) {
144 if (analyzeGlobalAux(I, GS, PhiUsers))
146 } else if (isa<SelectInst>(I)) {
147 if (analyzeGlobalAux(I, GS, PhiUsers))
149 } else if (const PHINode *PN = dyn_cast<PHINode>(I)) {
150 // PHI nodes we can check just like select or GEP instructions, but we
151 // have to be careful about infinite recursion.
152 if (PhiUsers.insert(PN).second) // Not already visited.
153 if (analyzeGlobalAux(I, GS, PhiUsers))
155 } else if (isa<CmpInst>(I)) {
156 GS.IsCompared = true;
157 } else if (const MemTransferInst *MTI = dyn_cast<MemTransferInst>(I)) {
158 if (MTI->isVolatile())
160 if (MTI->getArgOperand(0) == V)
161 GS.StoredType = GlobalStatus::Stored;
162 if (MTI->getArgOperand(1) == V)
164 } else if (const MemSetInst *MSI = dyn_cast<MemSetInst>(I)) {
165 assert(MSI->getArgOperand(0) == V && "Memset only takes one pointer!");
166 if (MSI->isVolatile())
168 GS.StoredType = GlobalStatus::Stored;
169 } else if (auto C = ImmutableCallSite(I)) {
174 return true; // Any other non-load instruction might take address!
176 } else if (const Constant *C = dyn_cast<Constant>(UR)) {
177 GS.HasNonInstructionUser = true;
178 // We might have a dead and dangling constant hanging off of here.
179 if (!isSafeToDestroyConstant(C))
182 GS.HasNonInstructionUser = true;
183 // Otherwise must be some other user.
191 GlobalStatus::GlobalStatus() = default;
193 bool GlobalStatus::analyzeGlobal(const Value *V, GlobalStatus &GS) {
194 SmallPtrSet<const PHINode *, 16> PhiUsers;
195 return analyzeGlobalAux(V, GS, PhiUsers);