200 lines · cpp
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-exception6//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 28using namespace llvm;29 30/// Return the stronger of the two ordering. If the two orderings are acquire31/// and release, then return AcquireRelease.32///33static 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 while constants cannot be cyclic, they can be tree-like, so we42/// should keep a visited set to avoid exponential runtime.43bool llvm::isSafeToDestroyConstant(const Constant *C) {44 SmallVector<const Constant *, 8> Worklist;45 SmallPtrSet<const Constant *, 8> Visited;46 Worklist.push_back(C);47 while (!Worklist.empty()) {48 const Constant *C = Worklist.pop_back_val();49 if (!Visited.insert(C).second)50 continue;51 if (isa<GlobalValue>(C) || isa<ConstantData>(C))52 return false;53 54 for (const User *U : C->users()) {55 if (const Constant *CU = dyn_cast<Constant>(U))56 Worklist.push_back(CU);57 else58 return false;59 }60 }61 return true;62}63 64static bool analyzeGlobalAux(const Value *V, GlobalStatus &GS,65 SmallPtrSetImpl<const Value *> &VisitedUsers) {66 if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(V))67 if (GV->isExternallyInitialized())68 GS.StoredType = GlobalStatus::StoredOnce;69 70 for (const Use &U : V->uses()) {71 const User *UR = U.getUser();72 if (const Constant *C = dyn_cast<Constant>(UR)) {73 const ConstantExpr *CE = dyn_cast<ConstantExpr>(C);74 if (CE && isa<PointerType>(CE->getType())) {75 // Recursively analyze pointer-typed constant expressions.76 // FIXME: Do we need to add constexpr selects to VisitedUsers?77 if (analyzeGlobalAux(CE, GS, VisitedUsers))78 return true;79 } else {80 // Ignore dead constant users.81 if (!isSafeToDestroyConstant(C))82 return true;83 }84 } else if (const Instruction *I = dyn_cast<Instruction>(UR)) {85 if (!GS.HasMultipleAccessingFunctions) {86 const Function *F = I->getParent()->getParent();87 if (!GS.AccessingFunction)88 GS.AccessingFunction = F;89 else if (GS.AccessingFunction != F)90 GS.HasMultipleAccessingFunctions = true;91 }92 if (const LoadInst *LI = dyn_cast<LoadInst>(I)) {93 GS.IsLoaded = true;94 // Don't hack on volatile loads.95 if (LI->isVolatile())96 return true;97 GS.Ordering = strongerOrdering(GS.Ordering, LI->getOrdering());98 } else if (const StoreInst *SI = dyn_cast<StoreInst>(I)) {99 // Don't allow a store OF the address, only stores TO the address.100 if (SI->getOperand(0) == V)101 return true;102 103 // Don't hack on volatile stores.104 if (SI->isVolatile())105 return true;106 107 ++GS.NumStores;108 109 GS.Ordering = strongerOrdering(GS.Ordering, SI->getOrdering());110 111 // If this is a direct store to the global (i.e., the global is a scalar112 // value, not an aggregate), keep more specific information about113 // stores.114 if (GS.StoredType != GlobalStatus::Stored) {115 const Value *Ptr = SI->getPointerOperand()->stripPointerCasts();116 if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(Ptr)) {117 Value *StoredVal = SI->getOperand(0);118 119 if (Constant *C = dyn_cast<Constant>(StoredVal)) {120 if (C->isThreadDependent()) {121 // The stored value changes between threads; don't track it.122 return true;123 }124 }125 126 if (GV->hasInitializer() && StoredVal == GV->getInitializer()) {127 if (GS.StoredType < GlobalStatus::InitializerStored)128 GS.StoredType = GlobalStatus::InitializerStored;129 } else if (isa<LoadInst>(StoredVal) &&130 cast<LoadInst>(StoredVal)->getOperand(0) == GV) {131 if (GS.StoredType < GlobalStatus::InitializerStored)132 GS.StoredType = GlobalStatus::InitializerStored;133 } else if (GS.StoredType < GlobalStatus::StoredOnce) {134 GS.StoredType = GlobalStatus::StoredOnce;135 GS.StoredOnceStore = SI;136 } else if (GS.StoredType == GlobalStatus::StoredOnce &&137 GS.getStoredOnceValue() == StoredVal) {138 // noop.139 } else {140 GS.StoredType = GlobalStatus::Stored;141 }142 } else {143 GS.StoredType = GlobalStatus::Stored;144 }145 }146 } else if (isa<GetElementPtrInst>(I) || isa<AddrSpaceCastInst>(I)) {147 // Skip over GEPs; we don't care about the type or offset148 // of the pointer.149 if (analyzeGlobalAux(I, GS, VisitedUsers))150 return true;151 } else if (isa<SelectInst>(I) || isa<PHINode>(I)) {152 // Look through selects and PHIs to find if the pointer is153 // conditionally accessed. Make sure we only visit an instruction154 // once; otherwise, we can get infinite recursion or exponential155 // compile time.156 if (VisitedUsers.insert(I).second)157 if (analyzeGlobalAux(I, GS, VisitedUsers))158 return true;159 } else if (isa<CmpInst>(I)) {160 GS.IsCompared = true;161 } else if (const MemTransferInst *MTI = dyn_cast<MemTransferInst>(I)) {162 if (MTI->isVolatile())163 return true;164 if (MTI->getArgOperand(0) == V)165 GS.StoredType = GlobalStatus::Stored;166 if (MTI->getArgOperand(1) == V)167 GS.IsLoaded = true;168 } else if (const MemSetInst *MSI = dyn_cast<MemSetInst>(I)) {169 assert(MSI->getArgOperand(0) == V && "Memset only takes one pointer!");170 if (MSI->isVolatile())171 return true;172 GS.StoredType = GlobalStatus::Stored;173 } else if (const auto *CB = dyn_cast<CallBase>(I)) {174 if (CB->getIntrinsicID() == Intrinsic::threadlocal_address) {175 if (analyzeGlobalAux(I, GS, VisitedUsers))176 return true;177 } else {178 if (!CB->isCallee(&U))179 return true;180 GS.IsLoaded = true;181 }182 } else {183 return true; // Any other non-load instruction might take address!184 }185 } else {186 // Otherwise must be some other user.187 return true;188 }189 }190 191 return false;192}193 194GlobalStatus::GlobalStatus() = default;195 196bool GlobalStatus::analyzeGlobal(const Value *V, GlobalStatus &GS) {197 SmallPtrSet<const Value *, 16> VisitedUsers;198 return analyzeGlobalAux(V, GS, VisitedUsers);199}200