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