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