lib/Transforms/Utils/GlobalStatus.cpp

   1 //===-- GlobalStatus.cpp - Compute status info for globals -----------------==//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9
  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/Transforms/Utils/GlobalStatus.h"
  22 #include "llvm/IR/Use.h"
  23 #include "llvm/IR/User.h"
  24 #include "llvm/IR/Value.h"
  25 #include "llvm/Support/AtomicOrdering.h"
  26 #include "llvm/Support/Casting.h"
  27 #include <algorithm>
  28 #include <cassert>
  29
  30 using namespace llvm;
  31
  32 /// Return the stronger of the two ordering. If the two orderings are acquire
  33 /// and release, then return AcquireRelease.
  34 ///
  35 static AtomicOrdering strongerOrdering(AtomicOrdering X, AtomicOrdering Y) {
  36   if ((X == AtomicOrdering::Acquire && Y == AtomicOrdering::Release) ||
  37       (Y == AtomicOrdering::Acquire && X == AtomicOrdering::Release))
  38     return AtomicOrdering::AcquireRelease;
  39   return (AtomicOrdering)std::max((unsigned)X, (unsigned)Y);
  40 }
  41
  42 /// It is safe to destroy a constant iff it is only used by constants itself.
  43 /// Note that constants cannot be cyclic, so this test is pretty easy to
  44 /// implement recursively.
  45 ///
  46 bool llvm::isSafeToDestroyConstant(const Constant *C) {
  47   if (isa<GlobalValue>(C))
  48     return false;
  49
  50   if (isa<ConstantData>(C))
  51     return false;
  52
  53   for (const User *U : C->users())
  54     if (const Constant *CU = dyn_cast<Constant>(U)) {
  55       if (!isSafeToDestroyConstant(CU))
  56         return false;
  57     } else
  58       return false;
  59   return true;
  60 }
  61
  62 static bool analyzeGlobalAux(const Value *V, GlobalStatus &GS,
  63                              SmallPtrSetImpl<const PHINode *> &PhiUsers) {
  64   if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(V))
  65     if (GV->isExternallyInitialized())
  66       GS.StoredType = GlobalStatus::StoredOnce;
  67
  68   for (const Use &U : V->uses()) {
  69     const User *UR = U.getUser();
  70     if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(UR)) {
  71       GS.HasNonInstructionUser = true;
  72
  73       // If the result of the constantexpr isn't pointer type, then we won't
  74       // know to expect it in various places.  Just reject early.
  75       if (!isa<PointerType>(CE->getType()))
  76         return true;
  77
  78       if (analyzeGlobalAux(CE, GS, PhiUsers))
  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)) {
 141         if (analyzeGlobalAux(I, GS, PhiUsers))
 142           return true;
 143       } else if (isa<GetElementPtrInst>(I)) {
 144         if (analyzeGlobalAux(I, GS, PhiUsers))
 145           return true;
 146       } else if (isa<SelectInst>(I)) {
 147         if (analyzeGlobalAux(I, GS, PhiUsers))
 148           return true;
 149       } else if (const PHINode *PN = dyn_cast<PHINode>(I)) {
 150         // PHI nodes we can check just like select or GEP instructions, but we
 151         // have to be careful about infinite recursion.
 152         if (PhiUsers.insert(PN).second) // Not already visited.
 153           if (analyzeGlobalAux(I, GS, PhiUsers))
 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 (auto C = ImmutableCallSite(I)) {
 170         if (!C.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 PHINode *, 16> PhiUsers;
 195   return analyzeGlobalAux(V, GS, PhiUsers);
 196 }