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/CallSite.h"
13 #include "llvm/IR/Constant.h"
14 #include "llvm/IR/Constants.h"
15 #include "llvm/IR/GlobalValue.h"
16 #include "llvm/IR/GlobalVariable.h"
17 #include "llvm/IR/InstrTypes.h"
18 #include "llvm/IR/Instruction.h"
19 #include "llvm/IR/Instructions.h"
20 #include "llvm/IR/IntrinsicInst.h"
21 #include "llvm/IR/Use.h"
22 #include "llvm/IR/User.h"
23 #include "llvm/IR/Value.h"
24 #include "llvm/Support/AtomicOrdering.h"
25 #include "llvm/Support/Casting.h"
26 #include <algorithm>
27 #include <cassert>
28 
29 using namespace llvm;
30 
31 /// Return the stronger of the two ordering. If the two orderings are acquire
32 /// and release, then return AcquireRelease.
33 ///
34 static AtomicOrdering strongerOrdering(AtomicOrdering X, AtomicOrdering Y) {
35   if ((X == AtomicOrdering::Acquire && Y == AtomicOrdering::Release) ||
36       (Y == AtomicOrdering::Acquire && X == AtomicOrdering::Release))
37     return AtomicOrdering::AcquireRelease;
38   return (AtomicOrdering)std::max((unsigned)X, (unsigned)Y);
39 }
40 
41 /// It is safe to destroy a constant iff it is only used by constants itself.
42 /// Note that constants cannot be cyclic, so this test is pretty easy to
43 /// implement recursively.
44 ///
45 bool llvm::isSafeToDestroyConstant(const Constant *C) {
46   if (isa<GlobalValue>(C))
47     return false;
48 
49   if (isa<ConstantData>(C))
50     return false;
51 
52   for (const User *U : C->users())
53     if (const Constant *CU = dyn_cast<Constant>(U)) {
54       if (!isSafeToDestroyConstant(CU))
55         return false;
56     } else
57       return false;
58   return true;
59 }
60 
61 static bool analyzeGlobalAux(const Value *V, GlobalStatus &GS,
62                              SmallPtrSetImpl<const Value *> &VisitedUsers) {
63   if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(V))
64     if (GV->isExternallyInitialized())
65       GS.StoredType = GlobalStatus::StoredOnce;
66 
67   for (const Use &U : V->uses()) {
68     const User *UR = U.getUser();
69     if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(UR)) {
70       GS.HasNonInstructionUser = true;
71 
72       // If the result of the constantexpr isn't pointer type, then we won't
73       // know to expect it in various places.  Just reject early.
74       if (!isa<PointerType>(CE->getType()))
75         return true;
76 
77       // FIXME: Do we need to add constexpr selects to VisitedUsers?
78       if (analyzeGlobalAux(CE, GS, VisitedUsers))
79         return true;
80     } else if (const Instruction *I = dyn_cast<Instruction>(UR)) {
81       if (!GS.HasMultipleAccessingFunctions) {
82         const Function *F = I->getParent()->getParent();
83         if (!GS.AccessingFunction)
84           GS.AccessingFunction = F;
85         else if (GS.AccessingFunction != F)
86           GS.HasMultipleAccessingFunctions = true;
87       }
88       if (const LoadInst *LI = dyn_cast<LoadInst>(I)) {
89         GS.IsLoaded = true;
90         // Don't hack on volatile loads.
91         if (LI->isVolatile())
92           return true;
93         GS.Ordering = strongerOrdering(GS.Ordering, LI->getOrdering());
94       } else if (const StoreInst *SI = dyn_cast<StoreInst>(I)) {
95         // Don't allow a store OF the address, only stores TO the address.
96         if (SI->getOperand(0) == V)
97           return true;
98 
99         // Don't hack on volatile stores.
100         if (SI->isVolatile())
101           return true;
102 
103         GS.Ordering = strongerOrdering(GS.Ordering, SI->getOrdering());
104 
105         // If this is a direct store to the global (i.e., the global is a scalar
106         // value, not an aggregate), keep more specific information about
107         // stores.
108         if (GS.StoredType != GlobalStatus::Stored) {
109           if (const GlobalVariable *GV =
110                   dyn_cast<GlobalVariable>(SI->getOperand(1))) {
111             Value *StoredVal = SI->getOperand(0);
112 
113             if (Constant *C = dyn_cast<Constant>(StoredVal)) {
114               if (C->isThreadDependent()) {
115                 // The stored value changes between threads; don't track it.
116                 return true;
117               }
118             }
119 
120             if (GV->hasInitializer() && StoredVal == GV->getInitializer()) {
121               if (GS.StoredType < GlobalStatus::InitializerStored)
122                 GS.StoredType = GlobalStatus::InitializerStored;
123             } else if (isa<LoadInst>(StoredVal) &&
124                        cast<LoadInst>(StoredVal)->getOperand(0) == GV) {
125               if (GS.StoredType < GlobalStatus::InitializerStored)
126                 GS.StoredType = GlobalStatus::InitializerStored;
127             } else if (GS.StoredType < GlobalStatus::StoredOnce) {
128               GS.StoredType = GlobalStatus::StoredOnce;
129               GS.StoredOnceValue = StoredVal;
130             } else if (GS.StoredType == GlobalStatus::StoredOnce &&
131                        GS.StoredOnceValue == StoredVal) {
132               // noop.
133             } else {
134               GS.StoredType = GlobalStatus::Stored;
135             }
136           } else {
137             GS.StoredType = GlobalStatus::Stored;
138           }
139         }
140       } else if (isa<BitCastInst>(I) || isa<GetElementPtrInst>(I)) {
141         // Skip over bitcasts and GEPs; we don't care about the type or offset
142         // of the pointer.
143         if (analyzeGlobalAux(I, GS, VisitedUsers))
144           return true;
145       } else if (isa<SelectInst>(I) || isa<PHINode>(I)) {
146         // Look through selects and PHIs to find if the pointer is
147         // conditionally accessed. Make sure we only visit an instruction
148         // once; otherwise, we can get infinite recursion or exponential
149         // compile time.
150         if (VisitedUsers.insert(I).second)
151           if (analyzeGlobalAux(I, GS, VisitedUsers))
152             return true;
153       } else if (isa<CmpInst>(I)) {
154         GS.IsCompared = true;
155       } else if (const MemTransferInst *MTI = dyn_cast<MemTransferInst>(I)) {
156         if (MTI->isVolatile())
157           return true;
158         if (MTI->getArgOperand(0) == V)
159           GS.StoredType = GlobalStatus::Stored;
160         if (MTI->getArgOperand(1) == V)
161           GS.IsLoaded = true;
162       } else if (const MemSetInst *MSI = dyn_cast<MemSetInst>(I)) {
163         assert(MSI->getArgOperand(0) == V && "Memset only takes one pointer!");
164         if (MSI->isVolatile())
165           return true;
166         GS.StoredType = GlobalStatus::Stored;
167       } else if (auto C = ImmutableCallSite(I)) {
168         if (!C.isCallee(&U))
169           return true;
170         GS.IsLoaded = true;
171       } else {
172         return true; // Any other non-load instruction might take address!
173       }
174     } else if (const Constant *C = dyn_cast<Constant>(UR)) {
175       GS.HasNonInstructionUser = true;
176       // We might have a dead and dangling constant hanging off of here.
177       if (!isSafeToDestroyConstant(C))
178         return true;
179     } else {
180       GS.HasNonInstructionUser = true;
181       // Otherwise must be some other user.
182       return true;
183     }
184   }
185 
186   return false;
187 }
188 
189 GlobalStatus::GlobalStatus() = default;
190 
191 bool GlobalStatus::analyzeGlobal(const Value *V, GlobalStatus &GS) {
192   SmallPtrSet<const Value *, 16> VisitedUsers;
193   return analyzeGlobalAux(V, GS, VisitedUsers);
194 }
195