1 //===-- GlobalStatus.cpp - Compute status info for globals -----------------==// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 9 #include "llvm/Transforms/Utils/GlobalStatus.h" 10 #include "llvm/ADT/SmallPtrSet.h" 11 #include "llvm/IR/BasicBlock.h" 12 #include "llvm/IR/Constant.h" 13 #include "llvm/IR/Constants.h" 14 #include "llvm/IR/GlobalValue.h" 15 #include "llvm/IR/GlobalVariable.h" 16 #include "llvm/IR/InstrTypes.h" 17 #include "llvm/IR/Instruction.h" 18 #include "llvm/IR/Instructions.h" 19 #include "llvm/IR/IntrinsicInst.h" 20 #include "llvm/IR/Use.h" 21 #include "llvm/IR/User.h" 22 #include "llvm/IR/Value.h" 23 #include "llvm/Support/AtomicOrdering.h" 24 #include "llvm/Support/Casting.h" 25 #include <algorithm> 26 #include <cassert> 27 28 using namespace llvm; 29 30 /// Return the stronger of the two ordering. If the two orderings are acquire 31 /// and release, then return AcquireRelease. 32 /// 33 static AtomicOrdering strongerOrdering(AtomicOrdering X, AtomicOrdering Y) { 34 if ((X == AtomicOrdering::Acquire && Y == AtomicOrdering::Release) || 35 (Y == AtomicOrdering::Acquire && X == AtomicOrdering::Release)) 36 return AtomicOrdering::AcquireRelease; 37 return (AtomicOrdering)std::max((unsigned)X, (unsigned)Y); 38 } 39 40 /// It is safe to destroy a constant iff it is only used by constants itself. 41 /// Note that constants cannot be cyclic, so this test is pretty easy to 42 /// implement recursively. 43 /// 44 bool llvm::isSafeToDestroyConstant(const Constant *C) { 45 if (isa<GlobalValue>(C)) 46 return false; 47 48 if (isa<ConstantData>(C)) 49 return false; 50 51 for (const User *U : C->users()) 52 if (const Constant *CU = dyn_cast<Constant>(U)) { 53 if (!isSafeToDestroyConstant(CU)) 54 return false; 55 } else 56 return false; 57 return true; 58 } 59 60 static bool analyzeGlobalAux(const Value *V, GlobalStatus &GS, 61 SmallPtrSetImpl<const Value *> &VisitedUsers) { 62 if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(V)) 63 if (GV->isExternallyInitialized()) 64 GS.StoredType = GlobalStatus::StoredOnce; 65 66 for (const Use &U : V->uses()) { 67 const User *UR = U.getUser(); 68 if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(UR)) { 69 GS.HasNonInstructionUser = true; 70 71 // If the result of the constantexpr isn't pointer type, then we won't 72 // know to expect it in various places. Just reject early. 73 if (!isa<PointerType>(CE->getType())) 74 return true; 75 76 // FIXME: Do we need to add constexpr selects to VisitedUsers? 77 if (analyzeGlobalAux(CE, GS, VisitedUsers)) 78 return true; 79 } else if (const Instruction *I = dyn_cast<Instruction>(UR)) { 80 if (!GS.HasMultipleAccessingFunctions) { 81 const Function *F = I->getParent()->getParent(); 82 if (!GS.AccessingFunction) 83 GS.AccessingFunction = F; 84 else if (GS.AccessingFunction != F) 85 GS.HasMultipleAccessingFunctions = true; 86 } 87 if (const LoadInst *LI = dyn_cast<LoadInst>(I)) { 88 GS.IsLoaded = true; 89 // Don't hack on volatile loads. 90 if (LI->isVolatile()) 91 return true; 92 GS.Ordering = strongerOrdering(GS.Ordering, LI->getOrdering()); 93 } else if (const StoreInst *SI = dyn_cast<StoreInst>(I)) { 94 // Don't allow a store OF the address, only stores TO the address. 95 if (SI->getOperand(0) == V) 96 return true; 97 98 // Don't hack on volatile stores. 99 if (SI->isVolatile()) 100 return true; 101 102 GS.Ordering = strongerOrdering(GS.Ordering, SI->getOrdering()); 103 104 // If this is a direct store to the global (i.e., the global is a scalar 105 // value, not an aggregate), keep more specific information about 106 // stores. 107 if (GS.StoredType != GlobalStatus::Stored) { 108 const Value *Ptr = SI->getPointerOperand(); 109 if (isa<ConstantExpr>(Ptr)) 110 Ptr = Ptr->stripPointerCasts(); 111 if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(Ptr)) { 112 Value *StoredVal = SI->getOperand(0); 113 114 if (Constant *C = dyn_cast<Constant>(StoredVal)) { 115 if (C->isThreadDependent()) { 116 // The stored value changes between threads; don't track it. 117 return true; 118 } 119 } 120 121 if (GV->hasInitializer() && StoredVal == GV->getInitializer()) { 122 if (GS.StoredType < GlobalStatus::InitializerStored) 123 GS.StoredType = GlobalStatus::InitializerStored; 124 } else if (isa<LoadInst>(StoredVal) && 125 cast<LoadInst>(StoredVal)->getOperand(0) == GV) { 126 if (GS.StoredType < GlobalStatus::InitializerStored) 127 GS.StoredType = GlobalStatus::InitializerStored; 128 } else if (GS.StoredType < GlobalStatus::StoredOnce) { 129 GS.StoredType = GlobalStatus::StoredOnce; 130 GS.StoredOnceStore = SI; 131 } else if (GS.StoredType == GlobalStatus::StoredOnce && 132 GS.getStoredOnceValue() == StoredVal) { 133 // noop. 134 } else { 135 GS.StoredType = GlobalStatus::Stored; 136 } 137 } else { 138 GS.StoredType = GlobalStatus::Stored; 139 } 140 } 141 } else if (isa<BitCastInst>(I) || isa<GetElementPtrInst>(I) || 142 isa<AddrSpaceCastInst>(I)) { 143 // Skip over bitcasts and GEPs; we don't care about the type or offset 144 // of the pointer. 145 if (analyzeGlobalAux(I, GS, VisitedUsers)) 146 return true; 147 } else if (isa<SelectInst>(I) || isa<PHINode>(I)) { 148 // Look through selects and PHIs to find if the pointer is 149 // conditionally accessed. Make sure we only visit an instruction 150 // once; otherwise, we can get infinite recursion or exponential 151 // compile time. 152 if (VisitedUsers.insert(I).second) 153 if (analyzeGlobalAux(I, GS, VisitedUsers)) 154 return true; 155 } else if (isa<CmpInst>(I)) { 156 GS.IsCompared = true; 157 } else if (const MemTransferInst *MTI = dyn_cast<MemTransferInst>(I)) { 158 if (MTI->isVolatile()) 159 return true; 160 if (MTI->getArgOperand(0) == V) 161 GS.StoredType = GlobalStatus::Stored; 162 if (MTI->getArgOperand(1) == V) 163 GS.IsLoaded = true; 164 } else if (const MemSetInst *MSI = dyn_cast<MemSetInst>(I)) { 165 assert(MSI->getArgOperand(0) == V && "Memset only takes one pointer!"); 166 if (MSI->isVolatile()) 167 return true; 168 GS.StoredType = GlobalStatus::Stored; 169 } else if (const auto *CB = dyn_cast<CallBase>(I)) { 170 if (!CB->isCallee(&U)) 171 return true; 172 GS.IsLoaded = true; 173 } else { 174 return true; // Any other non-load instruction might take address! 175 } 176 } else if (const Constant *C = dyn_cast<Constant>(UR)) { 177 GS.HasNonInstructionUser = true; 178 // We might have a dead and dangling constant hanging off of here. 179 if (!isSafeToDestroyConstant(C)) 180 return true; 181 } else { 182 GS.HasNonInstructionUser = true; 183 // Otherwise must be some other user. 184 return true; 185 } 186 } 187 188 return false; 189 } 190 191 GlobalStatus::GlobalStatus() = default; 192 193 bool GlobalStatus::analyzeGlobal(const Value *V, GlobalStatus &GS) { 194 SmallPtrSet<const Value *, 16> VisitedUsers; 195 return analyzeGlobalAux(V, GS, VisitedUsers); 196 } 197