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 == 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 /// 34 bool 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 50 static 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 179 bool GlobalStatus::analyzeGlobal(const Value *V, GlobalStatus &GS) { 180 SmallPtrSet<const PHINode *, 16> PhiUsers; 181 return analyzeGlobalAux(V, GS, PhiUsers); 182 } 183 184 GlobalStatus::GlobalStatus() 185 : IsCompared(false), IsLoaded(false), StoredType(NotStored), 186 StoredOnceValue(nullptr), AccessingFunction(nullptr), 187 HasMultipleAccessingFunctions(false), HasNonInstructionUser(false), 188 Ordering(AtomicOrdering::NotAtomic) {} 189
