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 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 (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 47 static 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) 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 172 bool GlobalStatus::analyzeGlobal(const Value *V, GlobalStatus &GS) { 173 SmallPtrSet<const PHINode *, 16> PhiUsers; 174 return analyzeGlobalAux(V, GS, PhiUsers); 175 } 176 177 GlobalStatus::GlobalStatus() 178 : IsCompared(false), IsLoaded(false), StoredType(NotStored), 179 StoredOnceValue(nullptr), AccessingFunction(nullptr), 180 HasMultipleAccessingFunctions(false), HasNonInstructionUser(false), 181 Ordering(NotAtomic) {} 182
