llvm/lib/Transforms/Utils/GlobalStatus.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-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 while constants cannot be cyclic, they can be tree-like, so we
  42 /// should keep a visited set to avoid exponential runtime.
  43 bool 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       else
  58         return false;
  59     }
  60   }
  61   return true;
  62 }
  63
  64 static 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 scalar
 112         // value, not an aggregate), keep more specific information about
 113         // 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<BitCastInst>(I) || isa<GetElementPtrInst>(I) ||
 147                  isa<AddrSpaceCastInst>(I)) {
 148         // Skip over bitcasts and GEPs; we don't care about the type or offset
 149         // of the pointer.
 150         if (analyzeGlobalAux(I, GS, VisitedUsers))
 151           return true;
 152       } else if (isa<SelectInst>(I) || isa<PHINode>(I)) {
 153         // Look through selects and PHIs to find if the pointer is
 154         // conditionally accessed. Make sure we only visit an instruction
 155         // once; otherwise, we can get infinite recursion or exponential
 156         // compile time.
 157         if (VisitedUsers.insert(I).second)
 158           if (analyzeGlobalAux(I, GS, VisitedUsers))
 159             return true;
 160       } else if (isa<CmpInst>(I)) {
 161         GS.IsCompared = true;
 162       } else if (const MemTransferInst *MTI = dyn_cast<MemTransferInst>(I)) {
 163         if (MTI->isVolatile())
 164           return true;
 165         if (MTI->getArgOperand(0) == V)
 166           GS.StoredType = GlobalStatus::Stored;
 167         if (MTI->getArgOperand(1) == V)
 168           GS.IsLoaded = true;
 169       } else if (const MemSetInst *MSI = dyn_cast<MemSetInst>(I)) {
 170         assert(MSI->getArgOperand(0) == V && "Memset only takes one pointer!");
 171         if (MSI->isVolatile())
 172           return true;
 173         GS.StoredType = GlobalStatus::Stored;
 174       } else if (const auto *CB = dyn_cast<CallBase>(I)) {
 175         if (!CB->isCallee(&U))
 176           return true;
 177         GS.IsLoaded = true;
 178       } else {
 179         return true; // Any other non-load instruction might take address!
 180       }
 181     } else {
 182       // Otherwise must be some other user.
 183       return true;
 184     }
 185   }
 186
 187   return false;
 188 }
 189
 190 GlobalStatus::GlobalStatus() = default;
 191
 192 bool GlobalStatus::analyzeGlobal(const Value *V, GlobalStatus &GS) {
 193   SmallPtrSet<const Value *, 16> VisitedUsers;
 194   return analyzeGlobalAux(V, GS, VisitedUsers);
 195 }