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/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 }