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