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 == Acquire && Y == Release)
24 return AcquireRelease;
25 if (Y == Acquire && X == Release)
26 return AcquireRelease;
27 return (AtomicOrdering)std::max(X, 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 for (const User *U : C->users())
39 if (const Constant *CU = dyn_cast<Constant>(U)) {
40 if (!isSafeToDestroyConstant(CU))
41 return false;
42 } else
43 return false;
44 return true;
45 }
46
analyzeGlobalAux(const Value * V,GlobalStatus & GS,SmallPtrSet<const PHINode *,16> & PhiUsers)47 static bool analyzeGlobalAux(const Value *V, GlobalStatus &GS,
48 SmallPtrSet<const PHINode *, 16> &PhiUsers) {
49 for (const Use &U : V->uses()) {
50 const User *UR = U.getUser();
51 if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(UR)) {
52 GS.HasNonInstructionUser = true;
53
54 // If the result of the constantexpr isn't pointer type, then we won't
55 // know to expect it in various places. Just reject early.
56 if (!isa<PointerType>(CE->getType()))
57 return true;
58
59 if (analyzeGlobalAux(CE, GS, PhiUsers))
60 return true;
61 } else if (const Instruction *I = dyn_cast<Instruction>(UR)) {
62 if (!GS.HasMultipleAccessingFunctions) {
63 const Function *F = I->getParent()->getParent();
64 if (!GS.AccessingFunction)
65 GS.AccessingFunction = F;
66 else if (GS.AccessingFunction != F)
67 GS.HasMultipleAccessingFunctions = true;
68 }
69 if (const LoadInst *LI = dyn_cast<LoadInst>(I)) {
70 GS.IsLoaded = true;
71 // Don't hack on volatile loads.
72 if (LI->isVolatile())
73 return true;
74 GS.Ordering = strongerOrdering(GS.Ordering, LI->getOrdering());
75 } else if (const StoreInst *SI = dyn_cast<StoreInst>(I)) {
76 // Don't allow a store OF the address, only stores TO the address.
77 if (SI->getOperand(0) == V)
78 return true;
79
80 // Don't hack on volatile stores.
81 if (SI->isVolatile())
82 return true;
83
84 GS.Ordering = strongerOrdering(GS.Ordering, SI->getOrdering());
85
86 // If this is a direct store to the global (i.e., the global is a scalar
87 // value, not an aggregate), keep more specific information about
88 // stores.
89 if (GS.StoredType != GlobalStatus::Stored) {
90 if (const GlobalVariable *GV =
91 dyn_cast<GlobalVariable>(SI->getOperand(1))) {
92 Value *StoredVal = SI->getOperand(0);
93
94 if (Constant *C = dyn_cast<Constant>(StoredVal)) {
95 if (C->isThreadDependent()) {
96 // The stored value changes between threads; don't track it.
97 return true;
98 }
99 }
100
101 if (StoredVal == GV->getInitializer()) {
102 if (GS.StoredType < GlobalStatus::InitializerStored)
103 GS.StoredType = GlobalStatus::InitializerStored;
104 } else if (isa<LoadInst>(StoredVal) &&
105 cast<LoadInst>(StoredVal)->getOperand(0) == GV) {
106 if (GS.StoredType < GlobalStatus::InitializerStored)
107 GS.StoredType = GlobalStatus::InitializerStored;
108 } else if (GS.StoredType < GlobalStatus::StoredOnce) {
109 GS.StoredType = GlobalStatus::StoredOnce;
110 GS.StoredOnceValue = StoredVal;
111 } else if (GS.StoredType == GlobalStatus::StoredOnce &&
112 GS.StoredOnceValue == StoredVal) {
113 // noop.
114 } else {
115 GS.StoredType = GlobalStatus::Stored;
116 }
117 } else {
118 GS.StoredType = GlobalStatus::Stored;
119 }
120 }
121 } else if (isa<BitCastInst>(I)) {
122 if (analyzeGlobalAux(I, GS, PhiUsers))
123 return true;
124 } else if (isa<GetElementPtrInst>(I)) {
125 if (analyzeGlobalAux(I, GS, PhiUsers))
126 return true;
127 } else if (isa<SelectInst>(I)) {
128 if (analyzeGlobalAux(I, GS, PhiUsers))
129 return true;
130 } else if (const PHINode *PN = dyn_cast<PHINode>(I)) {
131 // PHI nodes we can check just like select or GEP instructions, but we
132 // have to be careful about infinite recursion.
133 if (PhiUsers.insert(PN)) // Not already visited.
134 if (analyzeGlobalAux(I, GS, PhiUsers))
135 return true;
136 } else if (isa<CmpInst>(I)) {
137 GS.IsCompared = true;
138 } else if (const MemTransferInst *MTI = dyn_cast<MemTransferInst>(I)) {
139 if (MTI->isVolatile())
140 return true;
141 if (MTI->getArgOperand(0) == V)
142 GS.StoredType = GlobalStatus::Stored;
143 if (MTI->getArgOperand(1) == V)
144 GS.IsLoaded = true;
145 } else if (const MemSetInst *MSI = dyn_cast<MemSetInst>(I)) {
146 assert(MSI->getArgOperand(0) == V && "Memset only takes one pointer!");
147 if (MSI->isVolatile())
148 return true;
149 GS.StoredType = GlobalStatus::Stored;
150 } else if (ImmutableCallSite C = I) {
151 if (!C.isCallee(&U))
152 return true;
153 GS.IsLoaded = true;
154 } else {
155 return true; // Any other non-load instruction might take address!
156 }
157 } else if (const Constant *C = dyn_cast<Constant>(UR)) {
158 GS.HasNonInstructionUser = true;
159 // We might have a dead and dangling constant hanging off of here.
160 if (!isSafeToDestroyConstant(C))
161 return true;
162 } else {
163 GS.HasNonInstructionUser = true;
164 // Otherwise must be some other user.
165 return true;
166 }
167 }
168
169 return false;
170 }
171
analyzeGlobal(const Value * V,GlobalStatus & GS)172 bool GlobalStatus::analyzeGlobal(const Value *V, GlobalStatus &GS) {
173 SmallPtrSet<const PHINode *, 16> PhiUsers;
174 return analyzeGlobalAux(V, GS, PhiUsers);
175 }
176
GlobalStatus()177 GlobalStatus::GlobalStatus()
178 : IsCompared(false), IsLoaded(false), StoredType(NotStored),
179 StoredOnceValue(nullptr), AccessingFunction(nullptr),
180 HasMultipleAccessingFunctions(false), HasNonInstructionUser(false),
181 Ordering(NotAtomic) {}
182