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