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