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