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