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