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