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 17 using namespace llvm; 18 19 /// Return the stronger of the two ordering. If the two orderings are acquire 20 /// and release, then return AcquireRelease. 21 /// 22 static 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 /// 34 bool 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 48 static 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 174 bool GlobalStatus::analyzeGlobal(const Value *V, GlobalStatus &GS) { 175 SmallPtrSet<const PHINode *, 16> PhiUsers; 176 return analyzeGlobalAux(V, GS, PhiUsers); 177 } 178 179 GlobalStatus::GlobalStatus() 180 : IsCompared(false), IsLoaded(false), StoredType(NotStored), 181 StoredOnceValue(0), AccessingFunction(0), 182 HasMultipleAccessingFunctions(false), HasNonInstructionUser(false), 183 Ordering(NotAtomic) {} 184