LLVM  15.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 
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"
24 #include "llvm/Support/Casting.h"
25 #include <algorithm>
26 #include <cassert>
27 
28 using namespace llvm;
29 
30 /// Return the stronger of the two ordering. If the two orderings are acquire
31 /// and release, then return AcquireRelease.
32 ///
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 
64 static 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 
190 GlobalStatus::GlobalStatus() = default;
191 
193  SmallPtrSet<const Value *, 16> VisitedUsers;
194  return analyzeGlobalAux(V, GS, VisitedUsers);
195 }
llvm::AtomicOrdering::AcquireRelease
@ AcquireRelease
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
IntrinsicInst.h
AtomicOrdering.h
llvm::MemTransferInst
This class wraps the llvm.memcpy/memmove intrinsics.
Definition: IntrinsicInst.h:1022
llvm::Function
Definition: Function.h:60
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1185
llvm::GlobalVariable
Definition: GlobalVariable.h:39
llvm::GlobalStatus::analyzeGlobal
static bool analyzeGlobal(const Value *V, GlobalStatus &GS)
Look at all uses of the global and fill in the GlobalStatus structure.
Definition: GlobalStatus.cpp:192
llvm::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:450
llvm::max
Expected< ExpressionValue > max(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
Definition: FileCheck.cpp:337
llvm::SmallVectorImpl::pop_back_val
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:654
Use.h
F
#define F(x, y, z)
Definition: MD5.cpp:55
Instruction.h
llvm::GlobalStatus
As we analyze each global, keep track of some information about it.
Definition: GlobalStatus.h:30
GlobalValue.h
Constants.h
llvm::User
Definition: User.h:44
C
(vector float) vec_cmpeq(*A, *B) C
Definition: README_ALTIVEC.txt:86
InstrTypes.h
Y
static GCMetadataPrinterRegistry::Add< OcamlGCMetadataPrinter > Y("ocaml", "ocaml 3.10-compatible collector")
strongerOrdering
static AtomicOrdering strongerOrdering(AtomicOrdering X, AtomicOrdering Y)
Return the stronger of the two ordering.
Definition: GlobalStatus.cpp:33
llvm::Value::uses
iterator_range< use_iterator > uses()
Definition: Value.h:376
llvm::Instruction
Definition: Instruction.h:42
llvm::AtomicOrdering::Acquire
@ Acquire
SmallPtrSet.h
llvm::isSafeToDestroyConstant
bool isSafeToDestroyConstant(const Constant *C)
It is safe to destroy a constant iff it is only used by constants itself.
Definition: GlobalStatus.cpp:43
X
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
llvm::MemSetInst
This class wraps the llvm.memset and llvm.memset.inline intrinsics.
Definition: IntrinsicInst.h:989
llvm::AtomicOrdering
AtomicOrdering
Atomic ordering for LLVM's memory model.
Definition: AtomicOrdering.h:56
BasicBlock.h
llvm::StoreInst
An instruction for storing to memory.
Definition: Instructions.h:297
llvm::Constant
This is an important base class in LLVM.
Definition: Constant.h:41
GlobalStatus.h
I
#define I(x, y, z)
Definition: MD5.cpp:58
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
SI
StandardInstrumentations SI(Debug, VerifyEach)
llvm::GlobalStatus::Stored
@ Stored
This global is stored to by multiple values or something else that we cannot track.
Definition: GlobalStatus.h:58
llvm::GlobalStatus::InitializerStored
@ InitializerStored
This global is stored to, but the only thing stored is the constant it was initialized with.
Definition: GlobalStatus.h:48
llvm::LoadInst
An instruction for reading from memory.
Definition: Instructions.h:173
llvm::AtomicOrdering::Release
@ Release
analyzeGlobalAux
static bool analyzeGlobalAux(const Value *V, GlobalStatus &GS, SmallPtrSetImpl< const Value * > &VisitedUsers)
Definition: GlobalStatus.cpp:64
Constant.h
llvm::ConstantExpr
A constant value that is initialized with an expression using other constant values.
Definition: Constants.h:972
llvm::X86AS::GS
@ GS
Definition: X86.h:191
GlobalVariable.h
Casting.h
llvm::GlobalStatus::GlobalStatus
GlobalStatus()
llvm::GlobalStatus::StoredOnce
@ StoredOnce
This global is stored to, but only its initializer and one other value is ever stored to it.
Definition: GlobalStatus.h:54
Instructions.h
User.h
llvm::SmallPtrSetImpl< const Value * >
Value.h
CU
Definition: AArch64AsmBackend.cpp:504
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
llvm::Value::users
iterator_range< user_iterator > users()
Definition: Value.h:421
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
llvm::SmallPtrSetImpl::insert
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:365