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/GlobalVariable.h"
  14 #include "llvm/IR/IntrinsicInst.h"
  15 #include "llvm/Transforms/Utils/GlobalStatus.h"
  16
  17 using namespace llvm;
  18
  19 /// Return the stronger of the two ordering. If the two orderings are acquire
  20 /// and release, then return AcquireRelease.
  21 ///
  22 static AtomicOrdering strongerOrdering(AtomicOrdering X, AtomicOrdering Y) {
  23   if (X == Acquire && Y == Release)
  24     return AcquireRelease;
  25   if (Y == Acquire && X == Release)
  26     return AcquireRelease;
  27   return (AtomicOrdering)std::max(X, Y);
  28 }
  29
  30 /// It is safe to destroy a constant iff it is only used by constants itself.
  31 /// Note that constants cannot be cyclic, so this test is pretty easy to
  32 /// implement recursively.
  33 ///
  34 bool llvm::isSafeToDestroyConstant(const Constant *C) {
  35   if (isa<GlobalValue>(C))
  36     return false;
  37
  38   if (isa<ConstantInt>(C) || isa<ConstantFP>(C))
  39     return false;
  40
  41   for (const User *U : C->users())
  42     if (const Constant *CU = dyn_cast<Constant>(U)) {
  43       if (!isSafeToDestroyConstant(CU))
  44         return false;
  45     } else
  46       return false;
  47   return true;
  48 }
  49
  50 static bool analyzeGlobalAux(const Value *V, GlobalStatus &GS,
  51                              SmallPtrSetImpl<const PHINode *> &PhiUsers) {
  52   if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(V))
  53     if (GV->isExternallyInitialized())
  54       GS.StoredType = GlobalStatus::StoredOnce;
  55
  56   for (const Use &U : V->uses()) {
  57     const User *UR = U.getUser();
  58     if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(UR)) {
  59       GS.HasNonInstructionUser = true;
  60
  61       // If the result of the constantexpr isn't pointer type, then we won't
  62       // know to expect it in various places.  Just reject early.
  63       if (!isa<PointerType>(CE->getType()))
  64         return true;
  65
  66       if (analyzeGlobalAux(CE, GS, PhiUsers))
  67         return true;
  68     } else if (const Instruction *I = dyn_cast<Instruction>(UR)) {
  69       if (!GS.HasMultipleAccessingFunctions) {
  70         const Function *F = I->getParent()->getParent();
  71         if (!GS.AccessingFunction)
  72           GS.AccessingFunction = F;
  73         else if (GS.AccessingFunction != F)
  74           GS.HasMultipleAccessingFunctions = true;
  75       }
  76       if (const LoadInst *LI = dyn_cast<LoadInst>(I)) {
  77         GS.IsLoaded = true;
  78         // Don't hack on volatile loads.
  79         if (LI->isVolatile())
  80           return true;
  81         GS.Ordering = strongerOrdering(GS.Ordering, LI->getOrdering());
  82       } else if (const StoreInst *SI = dyn_cast<StoreInst>(I)) {
  83         // Don't allow a store OF the address, only stores TO the address.
  84         if (SI->getOperand(0) == V)
  85           return true;
  86
  87         // Don't hack on volatile stores.
  88         if (SI->isVolatile())
  89           return true;
  90
  91         GS.Ordering = strongerOrdering(GS.Ordering, SI->getOrdering());
  92
  93         // If this is a direct store to the global (i.e., the global is a scalar
  94         // value, not an aggregate), keep more specific information about
  95         // stores.
  96         if (GS.StoredType != GlobalStatus::Stored) {
  97           if (const GlobalVariable *GV =
  98                   dyn_cast<GlobalVariable>(SI->getOperand(1))) {
  99             Value *StoredVal = SI->getOperand(0);
 100
 101             if (Constant *C = dyn_cast<Constant>(StoredVal)) {
 102               if (C->isThreadDependent()) {
 103                 // The stored value changes between threads; don't track it.
 104                 return true;
 105               }
 106             }
 107
 108             if (StoredVal == GV->getInitializer()) {
 109               if (GS.StoredType < GlobalStatus::InitializerStored)
 110                 GS.StoredType = GlobalStatus::InitializerStored;
 111             } else if (isa<LoadInst>(StoredVal) &&
 112                        cast<LoadInst>(StoredVal)->getOperand(0) == GV) {
 113               if (GS.StoredType < GlobalStatus::InitializerStored)
 114                 GS.StoredType = GlobalStatus::InitializerStored;
 115             } else if (GS.StoredType < GlobalStatus::StoredOnce) {
 116               GS.StoredType = GlobalStatus::StoredOnce;
 117               GS.StoredOnceValue = StoredVal;
 118             } else if (GS.StoredType == GlobalStatus::StoredOnce &&
 119                        GS.StoredOnceValue == StoredVal) {
 120               // noop.
 121             } else {
 122               GS.StoredType = GlobalStatus::Stored;
 123             }
 124           } else {
 125             GS.StoredType = GlobalStatus::Stored;
 126           }
 127         }
 128       } else if (isa<BitCastInst>(I)) {
 129         if (analyzeGlobalAux(I, GS, PhiUsers))
 130           return true;
 131       } else if (isa<GetElementPtrInst>(I)) {
 132         if (analyzeGlobalAux(I, GS, PhiUsers))
 133           return true;
 134       } else if (isa<SelectInst>(I)) {
 135         if (analyzeGlobalAux(I, GS, PhiUsers))
 136           return true;
 137       } else if (const PHINode *PN = dyn_cast<PHINode>(I)) {
 138         // PHI nodes we can check just like select or GEP instructions, but we
 139         // have to be careful about infinite recursion.
 140         if (PhiUsers.insert(PN).second) // Not already visited.
 141           if (analyzeGlobalAux(I, GS, PhiUsers))
 142             return true;
 143       } else if (isa<CmpInst>(I)) {
 144         GS.IsCompared = true;
 145       } else if (const MemTransferInst *MTI = dyn_cast<MemTransferInst>(I)) {
 146         if (MTI->isVolatile())
 147           return true;
 148         if (MTI->getArgOperand(0) == V)
 149           GS.StoredType = GlobalStatus::Stored;
 150         if (MTI->getArgOperand(1) == V)
 151           GS.IsLoaded = true;
 152       } else if (const MemSetInst *MSI = dyn_cast<MemSetInst>(I)) {
 153         assert(MSI->getArgOperand(0) == V && "Memset only takes one pointer!");
 154         if (MSI->isVolatile())
 155           return true;
 156         GS.StoredType = GlobalStatus::Stored;
 157       } else if (auto C = ImmutableCallSite(I)) {
 158         if (!C.isCallee(&U))
 159           return true;
 160         GS.IsLoaded = true;
 161       } else {
 162         return true; // Any other non-load instruction might take address!
 163       }
 164     } else if (const Constant *C = dyn_cast<Constant>(UR)) {
 165       GS.HasNonInstructionUser = true;
 166       // We might have a dead and dangling constant hanging off of here.
 167       if (!isSafeToDestroyConstant(C))
 168         return true;
 169     } else {
 170       GS.HasNonInstructionUser = true;
 171       // Otherwise must be some other user.
 172       return true;
 173     }
 174   }
 175
 176   return false;
 177 }
 178
 179 bool GlobalStatus::analyzeGlobal(const Value *V, GlobalStatus &GS) {
 180   SmallPtrSet<const PHINode *, 16> PhiUsers;
 181   return analyzeGlobalAux(V, GS, PhiUsers);
 182 }
 183
 184 GlobalStatus::GlobalStatus()
 185     : IsCompared(false), IsLoaded(false), StoredType(NotStored),
 186       StoredOnceValue(nullptr), AccessingFunction(nullptr),
 187       HasMultipleAccessingFunctions(false), HasNonInstructionUser(false),
 188       Ordering(NotAtomic) {}