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.Ordering = strongerOrdering(GS.Ordering, SI->getOrdering());
108 
109         // If this is a direct store to the global (i.e., the global is a scalar
110         // value, not an aggregate), keep more specific information about
111         // stores.
112         if (GS.StoredType != GlobalStatus::Stored) {
113           const Value *Ptr = SI->getPointerOperand()->stripPointerCasts();
114           if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(Ptr)) {
115             Value *StoredVal = SI->getOperand(0);
116 
117             if (Constant *C = dyn_cast<Constant>(StoredVal)) {
118               if (C->isThreadDependent()) {
119                 // The stored value changes between threads; don't track it.
120                 return true;
121               }
122             }
123 
124             if (GV->hasInitializer() && StoredVal == GV->getInitializer()) {
125               if (GS.StoredType < GlobalStatus::InitializerStored)
126                 GS.StoredType = GlobalStatus::InitializerStored;
127             } else if (isa<LoadInst>(StoredVal) &&
128                        cast<LoadInst>(StoredVal)->getOperand(0) == GV) {
129               if (GS.StoredType < GlobalStatus::InitializerStored)
130                 GS.StoredType = GlobalStatus::InitializerStored;
131             } else if (GS.StoredType < GlobalStatus::StoredOnce) {
132               GS.StoredType = GlobalStatus::StoredOnce;
133               GS.StoredOnceStore = SI;
134             } else if (GS.StoredType == GlobalStatus::StoredOnce &&
135                        GS.getStoredOnceValue() == StoredVal) {
136               // noop.
137             } else {
138               GS.StoredType = GlobalStatus::Stored;
139             }
140           } else {
141             GS.StoredType = GlobalStatus::Stored;
142           }
143         }
144       } else if (isa<BitCastInst>(I) || isa<GetElementPtrInst>(I) ||
145                  isa<AddrSpaceCastInst>(I)) {
146         // Skip over bitcasts and GEPs; we don't care about the type or offset
147         // of the pointer.
148         if (analyzeGlobalAux(I, GS, VisitedUsers))
149           return true;
150       } else if (isa<SelectInst>(I) || isa<PHINode>(I)) {
151         // Look through selects and PHIs to find if the pointer is
152         // conditionally accessed. Make sure we only visit an instruction
153         // once; otherwise, we can get infinite recursion or exponential
154         // compile time.
155         if (VisitedUsers.insert(I).second)
156           if (analyzeGlobalAux(I, GS, VisitedUsers))
157             return true;
158       } else if (isa<CmpInst>(I)) {
159         GS.IsCompared = true;
160       } else if (const MemTransferInst *MTI = dyn_cast<MemTransferInst>(I)) {
161         if (MTI->isVolatile())
162           return true;
163         if (MTI->getArgOperand(0) == V)
164           GS.StoredType = GlobalStatus::Stored;
165         if (MTI->getArgOperand(1) == V)
166           GS.IsLoaded = true;
167       } else if (const MemSetInst *MSI = dyn_cast<MemSetInst>(I)) {
168         assert(MSI->getArgOperand(0) == V && "Memset only takes one pointer!");
169         if (MSI->isVolatile())
170           return true;
171         GS.StoredType = GlobalStatus::Stored;
172       } else if (const auto *CB = dyn_cast<CallBase>(I)) {
173         if (!CB->isCallee(&U))
174           return true;
175         GS.IsLoaded = true;
176       } else {
177         return true; // Any other non-load instruction might take address!
178       }
179     } else {
180       // Otherwise must be some other user.
181       return true;
182     }
183   }
184 
185   return false;
186 }
187 
188 GlobalStatus::GlobalStatus() = default;
189 
190 bool GlobalStatus::analyzeGlobal(const Value *V, GlobalStatus &GS) {
191   SmallPtrSet<const Value *, 16> VisitedUsers;
192   return analyzeGlobalAux(V, GS, VisitedUsers);
193 }
194