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