1259698Sdim//===-- GlobalStatus.cpp - Compute status info for globals -----------------==// 2259698Sdim// 3353358Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4353358Sdim// See https://llvm.org/LICENSE.txt for license information. 5353358Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6259698Sdim// 7259698Sdim//===----------------------------------------------------------------------===// 8259698Sdim 9321369Sdim#include "llvm/Transforms/Utils/GlobalStatus.h" 10259698Sdim#include "llvm/ADT/SmallPtrSet.h" 11259698Sdim#include "llvm/IR/BasicBlock.h" 12276479Sdim#include "llvm/IR/CallSite.h" 13321369Sdim#include "llvm/IR/Constant.h" 14321369Sdim#include "llvm/IR/Constants.h" 15321369Sdim#include "llvm/IR/GlobalValue.h" 16259698Sdim#include "llvm/IR/GlobalVariable.h" 17321369Sdim#include "llvm/IR/InstrTypes.h" 18321369Sdim#include "llvm/IR/Instruction.h" 19321369Sdim#include "llvm/IR/Instructions.h" 20259698Sdim#include "llvm/IR/IntrinsicInst.h" 21321369Sdim#include "llvm/IR/Use.h" 22321369Sdim#include "llvm/IR/User.h" 23321369Sdim#include "llvm/IR/Value.h" 24321369Sdim#include "llvm/Support/AtomicOrdering.h" 25321369Sdim#include "llvm/Support/Casting.h" 26321369Sdim#include <algorithm> 27321369Sdim#include <cassert> 28259698Sdim 29259698Sdimusing namespace llvm; 30259698Sdim 31259698Sdim/// Return the stronger of the two ordering. If the two orderings are acquire 32259698Sdim/// and release, then return AcquireRelease. 33259698Sdim/// 34259698Sdimstatic AtomicOrdering strongerOrdering(AtomicOrdering X, AtomicOrdering Y) { 35314564Sdim if ((X == AtomicOrdering::Acquire && Y == AtomicOrdering::Release) || 36314564Sdim (Y == AtomicOrdering::Acquire && X == AtomicOrdering::Release)) 37309124Sdim return AtomicOrdering::AcquireRelease; 38309124Sdim return (AtomicOrdering)std::max((unsigned)X, (unsigned)Y); 39259698Sdim} 40259698Sdim 41259698Sdim/// It is safe to destroy a constant iff it is only used by constants itself. 42259698Sdim/// Note that constants cannot be cyclic, so this test is pretty easy to 43259698Sdim/// implement recursively. 44259698Sdim/// 45259698Sdimbool llvm::isSafeToDestroyConstant(const Constant *C) { 46259698Sdim if (isa<GlobalValue>(C)) 47259698Sdim return false; 48259698Sdim 49314564Sdim if (isa<ConstantData>(C)) 50280031Sdim return false; 51280031Sdim 52276479Sdim for (const User *U : C->users()) 53276479Sdim if (const Constant *CU = dyn_cast<Constant>(U)) { 54259698Sdim if (!isSafeToDestroyConstant(CU)) 55259698Sdim return false; 56259698Sdim } else 57259698Sdim return false; 58259698Sdim return true; 59259698Sdim} 60259698Sdim 61259698Sdimstatic bool analyzeGlobalAux(const Value *V, GlobalStatus &GS, 62341825Sdim SmallPtrSetImpl<const Value *> &VisitedUsers) { 63296417Sdim if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(V)) 64296417Sdim if (GV->isExternallyInitialized()) 65296417Sdim GS.StoredType = GlobalStatus::StoredOnce; 66296417Sdim 67276479Sdim for (const Use &U : V->uses()) { 68276479Sdim const User *UR = U.getUser(); 69276479Sdim if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(UR)) { 70259698Sdim GS.HasNonInstructionUser = true; 71259698Sdim 72259698Sdim // If the result of the constantexpr isn't pointer type, then we won't 73259698Sdim // know to expect it in various places. Just reject early. 74259698Sdim if (!isa<PointerType>(CE->getType())) 75259698Sdim return true; 76259698Sdim 77341825Sdim // FIXME: Do we need to add constexpr selects to VisitedUsers? 78341825Sdim if (analyzeGlobalAux(CE, GS, VisitedUsers)) 79259698Sdim return true; 80276479Sdim } else if (const Instruction *I = dyn_cast<Instruction>(UR)) { 81259698Sdim if (!GS.HasMultipleAccessingFunctions) { 82259698Sdim const Function *F = I->getParent()->getParent(); 83276479Sdim if (!GS.AccessingFunction) 84259698Sdim GS.AccessingFunction = F; 85259698Sdim else if (GS.AccessingFunction != F) 86259698Sdim GS.HasMultipleAccessingFunctions = true; 87259698Sdim } 88259698Sdim if (const LoadInst *LI = dyn_cast<LoadInst>(I)) { 89259698Sdim GS.IsLoaded = true; 90259698Sdim // Don't hack on volatile loads. 91259698Sdim if (LI->isVolatile()) 92259698Sdim return true; 93259698Sdim GS.Ordering = strongerOrdering(GS.Ordering, LI->getOrdering()); 94259698Sdim } else if (const StoreInst *SI = dyn_cast<StoreInst>(I)) { 95259698Sdim // Don't allow a store OF the address, only stores TO the address. 96259698Sdim if (SI->getOperand(0) == V) 97259698Sdim return true; 98259698Sdim 99259698Sdim // Don't hack on volatile stores. 100259698Sdim if (SI->isVolatile()) 101259698Sdim return true; 102259698Sdim 103259698Sdim GS.Ordering = strongerOrdering(GS.Ordering, SI->getOrdering()); 104259698Sdim 105259698Sdim // If this is a direct store to the global (i.e., the global is a scalar 106259698Sdim // value, not an aggregate), keep more specific information about 107259698Sdim // stores. 108259698Sdim if (GS.StoredType != GlobalStatus::Stored) { 109259698Sdim if (const GlobalVariable *GV = 110259698Sdim dyn_cast<GlobalVariable>(SI->getOperand(1))) { 111259698Sdim Value *StoredVal = SI->getOperand(0); 112259698Sdim 113259698Sdim if (Constant *C = dyn_cast<Constant>(StoredVal)) { 114259698Sdim if (C->isThreadDependent()) { 115259698Sdim // The stored value changes between threads; don't track it. 116259698Sdim return true; 117259698Sdim } 118259698Sdim } 119259698Sdim 120309124Sdim if (GV->hasInitializer() && StoredVal == GV->getInitializer()) { 121259698Sdim if (GS.StoredType < GlobalStatus::InitializerStored) 122259698Sdim GS.StoredType = GlobalStatus::InitializerStored; 123259698Sdim } else if (isa<LoadInst>(StoredVal) && 124259698Sdim cast<LoadInst>(StoredVal)->getOperand(0) == GV) { 125259698Sdim if (GS.StoredType < GlobalStatus::InitializerStored) 126259698Sdim GS.StoredType = GlobalStatus::InitializerStored; 127259698Sdim } else if (GS.StoredType < GlobalStatus::StoredOnce) { 128259698Sdim GS.StoredType = GlobalStatus::StoredOnce; 129259698Sdim GS.StoredOnceValue = StoredVal; 130259698Sdim } else if (GS.StoredType == GlobalStatus::StoredOnce && 131259698Sdim GS.StoredOnceValue == StoredVal) { 132259698Sdim // noop. 133259698Sdim } else { 134259698Sdim GS.StoredType = GlobalStatus::Stored; 135259698Sdim } 136259698Sdim } else { 137259698Sdim GS.StoredType = GlobalStatus::Stored; 138259698Sdim } 139259698Sdim } 140341825Sdim } else if (isa<BitCastInst>(I) || isa<GetElementPtrInst>(I)) { 141341825Sdim // Skip over bitcasts and GEPs; we don't care about the type or offset 142341825Sdim // of the pointer. 143341825Sdim if (analyzeGlobalAux(I, GS, VisitedUsers)) 144259698Sdim return true; 145341825Sdim } else if (isa<SelectInst>(I) || isa<PHINode>(I)) { 146341825Sdim // Look through selects and PHIs to find if the pointer is 147341825Sdim // conditionally accessed. Make sure we only visit an instruction 148341825Sdim // once; otherwise, we can get infinite recursion or exponential 149341825Sdim // compile time. 150341825Sdim if (VisitedUsers.insert(I).second) 151341825Sdim if (analyzeGlobalAux(I, GS, VisitedUsers)) 152259698Sdim return true; 153259698Sdim } else if (isa<CmpInst>(I)) { 154259698Sdim GS.IsCompared = true; 155259698Sdim } else if (const MemTransferInst *MTI = dyn_cast<MemTransferInst>(I)) { 156259698Sdim if (MTI->isVolatile()) 157259698Sdim return true; 158259698Sdim if (MTI->getArgOperand(0) == V) 159259698Sdim GS.StoredType = GlobalStatus::Stored; 160259698Sdim if (MTI->getArgOperand(1) == V) 161259698Sdim GS.IsLoaded = true; 162259698Sdim } else if (const MemSetInst *MSI = dyn_cast<MemSetInst>(I)) { 163259698Sdim assert(MSI->getArgOperand(0) == V && "Memset only takes one pointer!"); 164259698Sdim if (MSI->isVolatile()) 165259698Sdim return true; 166259698Sdim GS.StoredType = GlobalStatus::Stored; 167288943Sdim } else if (auto C = ImmutableCallSite(I)) { 168276479Sdim if (!C.isCallee(&U)) 169259698Sdim return true; 170259698Sdim GS.IsLoaded = true; 171259698Sdim } else { 172259698Sdim return true; // Any other non-load instruction might take address! 173259698Sdim } 174276479Sdim } else if (const Constant *C = dyn_cast<Constant>(UR)) { 175259698Sdim GS.HasNonInstructionUser = true; 176259698Sdim // We might have a dead and dangling constant hanging off of here. 177259698Sdim if (!isSafeToDestroyConstant(C)) 178259698Sdim return true; 179259698Sdim } else { 180259698Sdim GS.HasNonInstructionUser = true; 181259698Sdim // Otherwise must be some other user. 182259698Sdim return true; 183259698Sdim } 184259698Sdim } 185259698Sdim 186259698Sdim return false; 187259698Sdim} 188259698Sdim 189321369SdimGlobalStatus::GlobalStatus() = default; 190321369Sdim 191259698Sdimbool GlobalStatus::analyzeGlobal(const Value *V, GlobalStatus &GS) { 192341825Sdim SmallPtrSet<const Value *, 16> VisitedUsers; 193341825Sdim return analyzeGlobalAux(V, GS, VisitedUsers); 194259698Sdim} 195