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