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