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 
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 ///
33 static 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((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.
43 bool llvm::isSafeToDestroyConstant(const Constant *C) {
44   SmallVector<const Constant *, 8> Worklist;
45   SmallPtrSet<const Constant *, 8> Visited;
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.
81         if (!isSafeToDestroyConstant(C))
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 
192 bool GlobalStatus::analyzeGlobal(const Value *V, GlobalStatus &GS) {
193   SmallPtrSet<const Value *, 16> VisitedUsers;
194   return analyzeGlobalAux(V, GS, VisitedUsers);
195 }
196