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/Transforms/Utils/GlobalStatus.h"
11 #include "llvm/ADT/SmallPtrSet.h"
12 #include "llvm/IR/BasicBlock.h"
13 #include "llvm/IR/CallSite.h"
14 #include "llvm/IR/Constant.h"
15 #include "llvm/IR/Constants.h"
16 #include "llvm/IR/GlobalValue.h"
17 #include "llvm/IR/GlobalVariable.h"
18 #include "llvm/IR/InstrTypes.h"
19 #include "llvm/IR/Instruction.h"
20 #include "llvm/IR/Instructions.h"
21 #include "llvm/IR/IntrinsicInst.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"
27 #include <algorithm>
28 #include <cassert>
29
30 using namespace llvm;
31
32 /// Return the stronger of the two ordering. If the two orderings are acquire
33 /// and release, then return AcquireRelease.
34 ///
strongerOrdering(AtomicOrdering X,AtomicOrdering Y)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);
40 }
41
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.
45 ///
isSafeToDestroyConstant(const Constant * C)46 bool llvm::isSafeToDestroyConstant(const Constant *C) {
47 if (isa<GlobalValue>(C))
48 return false;
49
50 if (isa<ConstantData>(C))
51 return false;
52
53 for (const User *U : C->users())
54 if (const Constant *CU = dyn_cast<Constant>(U)) {
55 if (!isSafeToDestroyConstant(CU))
56 return false;
57 } else
58 return false;
59 return true;
60 }
61
analyzeGlobalAux(const Value * V,GlobalStatus & GS,SmallPtrSetImpl<const Value * > & VisitedUsers)62 static bool analyzeGlobalAux(const Value *V, GlobalStatus &GS,
63 SmallPtrSetImpl<const Value *> &VisitedUsers) {
64 if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(V))
65 if (GV->isExternallyInitialized())
66 GS.StoredType = GlobalStatus::StoredOnce;
67
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;
72
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()))
76 return true;
77
78 // FIXME: Do we need to add constexpr selects to VisitedUsers?
79 if (analyzeGlobalAux(CE, GS, VisitedUsers))
80 return true;
81 } else if (const Instruction *I = dyn_cast<Instruction>(UR)) {
82 if (!GS.HasMultipleAccessingFunctions) {
83 const Function *F = I->getParent()->getParent();
84 if (!GS.AccessingFunction)
85 GS.AccessingFunction = F;
86 else if (GS.AccessingFunction != F)
87 GS.HasMultipleAccessingFunctions = true;
88 }
89 if (const LoadInst *LI = dyn_cast<LoadInst>(I)) {
90 GS.IsLoaded = true;
91 // Don't hack on volatile loads.
92 if (LI->isVolatile())
93 return true;
94 GS.Ordering = strongerOrdering(GS.Ordering, LI->getOrdering());
95 } else if (const StoreInst *SI = dyn_cast<StoreInst>(I)) {
96 // Don't allow a store OF the address, only stores TO the address.
97 if (SI->getOperand(0) == V)
98 return true;
99
100 // Don't hack on volatile stores.
101 if (SI->isVolatile())
102 return true;
103
104 GS.Ordering = strongerOrdering(GS.Ordering, SI->getOrdering());
105
106 // If this is a direct store to the global (i.e., the global is a scalar
107 // value, not an aggregate), keep more specific information about
108 // stores.
109 if (GS.StoredType != GlobalStatus::Stored) {
110 if (const GlobalVariable *GV =
111 dyn_cast<GlobalVariable>(SI->getOperand(1))) {
112 Value *StoredVal = SI->getOperand(0);
113
114 if (Constant *C = dyn_cast<Constant>(StoredVal)) {
115 if (C->isThreadDependent()) {
116 // The stored value changes between threads; don't track it.
117 return true;
118 }
119 }
120
121 if (GV->hasInitializer() && StoredVal == GV->getInitializer()) {
122 if (GS.StoredType < GlobalStatus::InitializerStored)
123 GS.StoredType = GlobalStatus::InitializerStored;
124 } else if (isa<LoadInst>(StoredVal) &&
125 cast<LoadInst>(StoredVal)->getOperand(0) == GV) {
126 if (GS.StoredType < GlobalStatus::InitializerStored)
127 GS.StoredType = GlobalStatus::InitializerStored;
128 } else if (GS.StoredType < GlobalStatus::StoredOnce) {
129 GS.StoredType = GlobalStatus::StoredOnce;
130 GS.StoredOnceValue = StoredVal;
131 } else if (GS.StoredType == GlobalStatus::StoredOnce &&
132 GS.StoredOnceValue == StoredVal) {
133 // noop.
134 } else {
135 GS.StoredType = GlobalStatus::Stored;
136 }
137 } else {
138 GS.StoredType = GlobalStatus::Stored;
139 }
140 }
141 } else if (isa<BitCastInst>(I) || isa<GetElementPtrInst>(I)) {
142 // Skip over bitcasts and GEPs; we don't care about the type or offset
143 // of the pointer.
144 if (analyzeGlobalAux(I, GS, VisitedUsers))
145 return true;
146 } else if (isa<SelectInst>(I) || isa<PHINode>(I)) {
147 // Look through selects and PHIs to find if the pointer is
148 // conditionally accessed. Make sure we only visit an instruction
149 // once; otherwise, we can get infinite recursion or exponential
150 // compile time.
151 if (VisitedUsers.insert(I).second)
152 if (analyzeGlobalAux(I, GS, VisitedUsers))
153 return true;
154 } else if (isa<CmpInst>(I)) {
155 GS.IsCompared = true;
156 } else if (const MemTransferInst *MTI = dyn_cast<MemTransferInst>(I)) {
157 if (MTI->isVolatile())
158 return true;
159 if (MTI->getArgOperand(0) == V)
160 GS.StoredType = GlobalStatus::Stored;
161 if (MTI->getArgOperand(1) == V)
162 GS.IsLoaded = true;
163 } else if (const MemSetInst *MSI = dyn_cast<MemSetInst>(I)) {
164 assert(MSI->getArgOperand(0) == V && "Memset only takes one pointer!");
165 if (MSI->isVolatile())
166 return true;
167 GS.StoredType = GlobalStatus::Stored;
168 } else if (auto C = ImmutableCallSite(I)) {
169 if (!C.isCallee(&U))
170 return true;
171 GS.IsLoaded = true;
172 } else {
173 return true; // Any other non-load instruction might take address!
174 }
175 } else if (const Constant *C = dyn_cast<Constant>(UR)) {
176 GS.HasNonInstructionUser = true;
177 // We might have a dead and dangling constant hanging off of here.
178 if (!isSafeToDestroyConstant(C))
179 return true;
180 } else {
181 GS.HasNonInstructionUser = true;
182 // Otherwise must be some other user.
183 return true;
184 }
185 }
186
187 return false;
188 }
189
190 GlobalStatus::GlobalStatus() = default;
191
analyzeGlobal(const Value * V,GlobalStatus & GS)192 bool GlobalStatus::analyzeGlobal(const Value *V, GlobalStatus &GS) {
193 SmallPtrSet<const Value *, 16> VisitedUsers;
194 return analyzeGlobalAux(V, GS, VisitedUsers);
195 }
196