1//===-- GlobalStatus.cpp - Compute status info for globals -----------------==//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8
9#include "llvm/Transforms/Utils/GlobalStatus.h"
10#include "llvm/ADT/SmallPtrSet.h"
11#include "llvm/IR/BasicBlock.h"
12#include "llvm/IR/Constant.h"
13#include "llvm/IR/Constants.h"
14#include "llvm/IR/GlobalValue.h"
15#include "llvm/IR/GlobalVariable.h"
16#include "llvm/IR/InstrTypes.h"
17#include "llvm/IR/Instruction.h"
18#include "llvm/IR/Instructions.h"
19#include "llvm/IR/IntrinsicInst.h"
20#include "llvm/IR/Use.h"
21#include "llvm/IR/User.h"
22#include "llvm/IR/Value.h"
23#include "llvm/Support/AtomicOrdering.h"
24#include "llvm/Support/Casting.h"
25#include <algorithm>
26#include <cassert>
27
28using namespace llvm;
29
30/// Return the stronger of the two ordering. If the two orderings are acquire
31/// and release, then return AcquireRelease.
32///
33static AtomicOrdering strongerOrdering(AtomicOrdering X, AtomicOrdering Y) {
34 if ((X == AtomicOrdering::Acquire && Y == AtomicOrdering::Release) ||
35 (Y == AtomicOrdering::Acquire && X == AtomicOrdering::Release))
36 return AtomicOrdering::AcquireRelease;
37 return (AtomicOrdering)std::max(a: (unsigned)X, b: (unsigned)Y);
38}
39
40/// It is safe to destroy a constant iff it is only used by constants itself.
41/// Note that while constants cannot be cyclic, they can be tree-like, so we
42/// should keep a visited set to avoid exponential runtime.
43bool llvm::isSafeToDestroyConstant(const Constant *C) {
44 SmallVector<const Constant *, 8> Worklist;
45 SmallPtrSet<const Constant *, 8> Visited;
46 Worklist.push_back(Elt: C);
47 while (!Worklist.empty()) {
48 const Constant *C = Worklist.pop_back_val();
49 if (!Visited.insert(Ptr: C).second)
50 continue;
51 if (isa<GlobalValue>(Val: C) || isa<ConstantData>(Val: C))
52 return false;
53
54 for (const User *U : C->users()) {
55 if (const Constant *CU = dyn_cast<Constant>(Val: U))
56 Worklist.push_back(Elt: CU);
57 else
58 return false;
59 }
60 }
61 return true;
62}
63
64static bool analyzeGlobalAux(const Value *V, GlobalStatus &GS,
65 SmallPtrSetImpl<const Value *> &VisitedUsers) {
66 if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(Val: V))
67 if (GV->isExternallyInitialized())
68 GS.StoredType = GlobalStatus::StoredOnce;
69
70 for (const Use &U : V->uses()) {
71 const User *UR = U.getUser();
72 if (const Constant *C = dyn_cast<Constant>(Val: UR)) {
73 const ConstantExpr *CE = dyn_cast<ConstantExpr>(Val: C);
74 if (CE && isa<PointerType>(Val: CE->getType())) {
75 // Recursively analyze pointer-typed constant expressions.
76 // FIXME: Do we need to add constexpr selects to VisitedUsers?
77 if (analyzeGlobalAux(V: CE, GS, VisitedUsers))
78 return true;
79 } else {
80 // Ignore dead constant users.
81 if (!isSafeToDestroyConstant(C))
82 return true;
83 }
84 } else if (const Instruction *I = dyn_cast<Instruction>(Val: UR)) {
85 if (!GS.HasMultipleAccessingFunctions) {
86 const Function *F = I->getParent()->getParent();
87 if (!GS.AccessingFunction)
88 GS.AccessingFunction = F;
89 else if (GS.AccessingFunction != F)
90 GS.HasMultipleAccessingFunctions = true;
91 }
92 if (const LoadInst *LI = dyn_cast<LoadInst>(Val: I)) {
93 GS.IsLoaded = true;
94 // Don't hack on volatile loads.
95 if (LI->isVolatile())
96 return true;
97 GS.Ordering = strongerOrdering(X: GS.Ordering, Y: LI->getOrdering());
98 } else if (const StoreInst *SI = dyn_cast<StoreInst>(Val: I)) {
99 // Don't allow a store OF the address, only stores TO the address.
100 if (SI->getOperand(i_nocapture: 0) == V)
101 return true;
102
103 // Don't hack on volatile stores.
104 if (SI->isVolatile())
105 return true;
106
107 ++GS.NumStores;
108
109 GS.Ordering = strongerOrdering(X: GS.Ordering, Y: SI->getOrdering());
110
111 // If this is a direct store to the global (i.e., the global is a scalar
112 // value, not an aggregate), keep more specific information about
113 // stores.
114 if (GS.StoredType != GlobalStatus::Stored) {
115 const Value *Ptr = SI->getPointerOperand()->stripPointerCasts();
116 if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(Val: Ptr)) {
117 Value *StoredVal = SI->getOperand(i_nocapture: 0);
118
119 if (Constant *C = dyn_cast<Constant>(Val: StoredVal)) {
120 if (C->isThreadDependent()) {
121 // The stored value changes between threads; don't track it.
122 return true;
123 }
124 }
125
126 if (GV->hasInitializer() && StoredVal == GV->getInitializer()) {
127 if (GS.StoredType < GlobalStatus::InitializerStored)
128 GS.StoredType = GlobalStatus::InitializerStored;
129 } else if (isa<LoadInst>(Val: StoredVal) &&
130 cast<LoadInst>(Val: StoredVal)->getOperand(i_nocapture: 0) == GV) {
131 if (GS.StoredType < GlobalStatus::InitializerStored)
132 GS.StoredType = GlobalStatus::InitializerStored;
133 } else if (GS.StoredType < GlobalStatus::StoredOnce) {
134 GS.StoredType = GlobalStatus::StoredOnce;
135 GS.StoredOnceStore = SI;
136 } else if (GS.StoredType == GlobalStatus::StoredOnce &&
137 GS.getStoredOnceValue() == StoredVal) {
138 // noop.
139 } else {
140 GS.StoredType = GlobalStatus::Stored;
141 }
142 } else {
143 GS.StoredType = GlobalStatus::Stored;
144 }
145 }
146 } else if (isa<GetElementPtrInst>(Val: I) || isa<AddrSpaceCastInst>(Val: I)) {
147 // Skip over GEPs; we don't care about the type or offset
148 // of the pointer.
149 if (analyzeGlobalAux(V: I, GS, VisitedUsers))
150 return true;
151 } else if (isa<SelectInst>(Val: I) || isa<PHINode>(Val: I)) {
152 // Look through selects and PHIs to find if the pointer is
153 // conditionally accessed. Make sure we only visit an instruction
154 // once; otherwise, we can get infinite recursion or exponential
155 // compile time.
156 if (VisitedUsers.insert(Ptr: I).second)
157 if (analyzeGlobalAux(V: I, GS, VisitedUsers))
158 return true;
159 } else if (isa<CmpInst>(Val: I)) {
160 GS.IsCompared = true;
161 } else if (const MemTransferInst *MTI = dyn_cast<MemTransferInst>(Val: I)) {
162 if (MTI->isVolatile())
163 return true;
164 if (MTI->getArgOperand(i: 0) == V)
165 GS.StoredType = GlobalStatus::Stored;
166 if (MTI->getArgOperand(i: 1) == V)
167 GS.IsLoaded = true;
168 } else if (const MemSetInst *MSI = dyn_cast<MemSetInst>(Val: I)) {
169 assert(MSI->getArgOperand(0) == V && "Memset only takes one pointer!");
170 if (MSI->isVolatile())
171 return true;
172 GS.StoredType = GlobalStatus::Stored;
173 } else if (const auto *CB = dyn_cast<CallBase>(Val: I)) {
174 if (CB->getIntrinsicID() == Intrinsic::threadlocal_address) {
175 if (analyzeGlobalAux(V: I, GS, VisitedUsers))
176 return true;
177 } else {
178 if (!CB->isCallee(U: &U))
179 return true;
180 GS.IsLoaded = true;
181 }
182 } else {
183 return true; // Any other non-load instruction might take address!
184 }
185 } else {
186 // Otherwise must be some other user.
187 return true;
188 }
189 }
190
191 return false;
192}
193
194GlobalStatus::GlobalStatus() = default;
195
196bool GlobalStatus::analyzeGlobal(const Value *V, GlobalStatus &GS) {
197 SmallPtrSet<const Value *, 16> VisitedUsers;
198 return analyzeGlobalAux(V, GS, VisitedUsers);
199}
200