LLVM 18.0.0git
GlobalStatus.cpp
Go to the documentation of this file.
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
11#include "llvm/IR/BasicBlock.h"
12#include "llvm/IR/Constant.h"
13#include "llvm/IR/Constants.h"
14#include "llvm/IR/GlobalValue.h"
16#include "llvm/IR/InstrTypes.h"
17#include "llvm/IR/Instruction.h"
20#include "llvm/IR/Use.h"
21#include "llvm/IR/User.h"
22#include "llvm/IR/Value.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///
34 if ((X == AtomicOrdering::Acquire && Y == AtomicOrdering::Release) ||
35 (Y == AtomicOrdering::Acquire && X == AtomicOrdering::Release))
36 return AtomicOrdering::AcquireRelease;
37 return (AtomicOrdering)std::max((unsigned)X, (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.
46 Worklist.push_back(C);
47 while (!Worklist.empty()) {
48 const Constant *C = Worklist.pop_back_val();
49 if (!Visited.insert(C).second)
50 continue;
51 if (isa<GlobalValue>(C) || isa<ConstantData>(C))
52 return false;
53
54 for (const User *U : C->users()) {
55 if (const Constant *CU = dyn_cast<Constant>(U))
56 Worklist.push_back(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>(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>(UR)) {
73 const ConstantExpr *CE = dyn_cast<ConstantExpr>(C);
74 if (CE && isa<PointerType>(CE->getType())) {
75 // Recursively analyze pointer-typed constant expressions.
76 // FIXME: Do we need to add constexpr selects to VisitedUsers?
77 if (analyzeGlobalAux(CE, GS, VisitedUsers))
78 return true;
79 } else {
80 // Ignore dead constant users.
82 return true;
83 }
84 } else if (const Instruction *I = dyn_cast<Instruction>(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>(I)) {
93 GS.IsLoaded = true;
94 // Don't hack on volatile loads.
95 if (LI->isVolatile())
96 return true;
97 GS.Ordering = strongerOrdering(GS.Ordering, LI->getOrdering());
98 } else if (const StoreInst *SI = dyn_cast<StoreInst>(I)) {
99 // Don't allow a store OF the address, only stores TO the address.
100 if (SI->getOperand(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(GS.Ordering, 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>(Ptr)) {
117 Value *StoredVal = SI->getOperand(0);
118
119 if (Constant *C = dyn_cast<Constant>(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>(StoredVal) &&
130 cast<LoadInst>(StoredVal)->getOperand(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<BitCastInst>(I) || isa<GetElementPtrInst>(I) ||
147 isa<AddrSpaceCastInst>(I)) {
148 // Skip over bitcasts and GEPs; we don't care about the type or offset
149 // of the pointer.
150 if (analyzeGlobalAux(I, GS, VisitedUsers))
151 return true;
152 } else if (isa<SelectInst>(I) || isa<PHINode>(I)) {
153 // Look through selects and PHIs to find if the pointer is
154 // conditionally accessed. Make sure we only visit an instruction
155 // once; otherwise, we can get infinite recursion or exponential
156 // compile time.
157 if (VisitedUsers.insert(I).second)
158 if (analyzeGlobalAux(I, GS, VisitedUsers))
159 return true;
160 } else if (isa<CmpInst>(I)) {
161 GS.IsCompared = true;
162 } else if (const MemTransferInst *MTI = dyn_cast<MemTransferInst>(I)) {
163 if (MTI->isVolatile())
164 return true;
165 if (MTI->getArgOperand(0) == V)
166 GS.StoredType = GlobalStatus::Stored;
167 if (MTI->getArgOperand(1) == V)
168 GS.IsLoaded = true;
169 } else if (const MemSetInst *MSI = dyn_cast<MemSetInst>(I)) {
170 assert(MSI->getArgOperand(0) == V && "Memset only takes one pointer!");
171 if (MSI->isVolatile())
172 return true;
173 GS.StoredType = GlobalStatus::Stored;
174 } else if (const auto *CB = dyn_cast<CallBase>(I)) {
175 if (!CB->isCallee(&U))
176 return true;
177 GS.IsLoaded = true;
178 } else {
179 return true; // Any other non-load instruction might take address!
180 }
181 } else {
182 // Otherwise must be some other user.
183 return true;
184 }
185 }
186
187 return false;
188}
189
191
194 return analyzeGlobalAux(V, GS, VisitedUsers);
195}
Atomic ordering constants.
This file contains the declarations for the subclasses of Constant, which represent the different fla...
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
static bool analyzeGlobalAux(const Value *V, GlobalStatus &GS, SmallPtrSetImpl< const Value * > &VisitedUsers)
static AtomicOrdering strongerOrdering(AtomicOrdering X, AtomicOrdering Y)
Return the stronger of the two ordering.
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
static GCMetadataPrinterRegistry::Add< OcamlGCMetadataPrinter > Y("ocaml", "ocaml 3.10-compatible collector")
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the SmallPtrSet class.
This defines the Use class.
A constant value that is initialized with an expression using other constant values.
Definition: Constants.h:1003
This is an important base class in LLVM.
Definition: Constant.h:41
An instruction for reading from memory.
Definition: Instructions.h:177
This class wraps the llvm.memset and llvm.memset.inline intrinsics.
This class wraps the llvm.memcpy/memmove intrinsics.
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:345
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:366
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:451
bool empty() const
Definition: SmallVector.h:94
void push_back(const T &Elt)
Definition: SmallVector.h:416
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1200
An instruction for storing to memory.
Definition: Instructions.h:301
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
LLVM Value Representation.
Definition: Value.h:74
@ C
The default llvm calling convention, compatible with C.
Definition: CallingConv.h:34
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
bool isSafeToDestroyConstant(const Constant *C)
It is safe to destroy a constant iff it is only used by constants itself.
AtomicOrdering
Atomic ordering for LLVM's memory model.
As we analyze each global, keep track of some information about it.
Definition: GlobalStatus.h:30
@ Stored
This global is stored to by multiple values or something else that we cannot track.
Definition: GlobalStatus.h:58
@ InitializerStored
This global is stored to, but the only thing stored is the constant it was initialized with.
Definition: GlobalStatus.h:48
@ StoredOnce
This global is stored to, but only its initializer and one other value is ever stored to it.
Definition: GlobalStatus.h:54
static bool analyzeGlobal(const Value *V, GlobalStatus &GS)
Look at all uses of the global and fill in the GlobalStatus structure.