lib/Transforms/ObjCARC/DependencyAnalysis.cpp

   1 //===- DependencyAnalysis.cpp - ObjC ARC Optimization ---------------------===//
   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 /// \file
  10 ///
  11 /// This file defines special dependency analysis routines used in Objective C
  12 /// ARC Optimizations.
  13 ///
  14 /// WARNING: This file knows about certain library functions. It recognizes them
  15 /// by name, and hardwires knowledge of their semantics.
  16 ///
  17 /// WARNING: This file knows about how certain Objective-C library functions are
  18 /// used. Naive LLVM IR transformations which would otherwise be
  19 /// behavior-preserving may break these assumptions.
  20 ///
  21 //===----------------------------------------------------------------------===//
  22
  23 #include "ObjCARC.h"
  24 #include "DependencyAnalysis.h"
  25 #include "ProvenanceAnalysis.h"
  26 #include "llvm/IR/CFG.h"
  27
  28 using namespace llvm;
  29 using namespace llvm::objcarc;
  30
  31 #define DEBUG_TYPE "objc-arc-dependency"
  32
  33 /// Test whether the given instruction can result in a reference count
  34 /// modification (positive or negative) for the pointer's object.
  35 bool llvm::objcarc::CanAlterRefCount(const Instruction *Inst, const Value *Ptr,
  36                                      ProvenanceAnalysis &PA,
  37                                      ARCInstKind Class) {
  38   switch (Class) {
  39   case ARCInstKind::Autorelease:
  40   case ARCInstKind::AutoreleaseRV:
  41   case ARCInstKind::IntrinsicUser:
  42   case ARCInstKind::User:
  43     // These operations never directly modify a reference count.
  44     return false;
  45   default: break;
  46   }
  47
  48   ImmutableCallSite CS(Inst);
  49   assert(CS && "Only calls can alter reference counts!");
  50
  51   // See if AliasAnalysis can help us with the call.
  52   AliasAnalysis::ModRefBehavior MRB = PA.getAA()->getModRefBehavior(CS);
  53   if (AliasAnalysis::onlyReadsMemory(MRB))
  54     return false;
  55   if (AliasAnalysis::onlyAccessesArgPointees(MRB)) {
  56     const DataLayout &DL = Inst->getModule()->getDataLayout();
  57     for (ImmutableCallSite::arg_iterator I = CS.arg_begin(), E = CS.arg_end();
  58          I != E; ++I) {
  59       const Value *Op = *I;
  60       if (IsPotentialRetainableObjPtr(Op, *PA.getAA()) &&
  61           PA.related(Ptr, Op, DL))
  62         return true;
  63     }
  64     return false;
  65   }
  66
  67   // Assume the worst.
  68   return true;
  69 }
  70
  71 bool llvm::objcarc::CanDecrementRefCount(const Instruction *Inst,
  72                                          const Value *Ptr,
  73                                          ProvenanceAnalysis &PA,
  74                                          ARCInstKind Class) {
  75   // First perform a quick check if Class can not touch ref counts.
  76   if (!CanDecrementRefCount(Class))
  77     return false;
  78
  79   // Otherwise, just use CanAlterRefCount for now.
  80   return CanAlterRefCount(Inst, Ptr, PA, Class);
  81 }
  82
  83 /// Test whether the given instruction can "use" the given pointer's object in a
  84 /// way that requires the reference count to be positive.
  85 bool llvm::objcarc::CanUse(const Instruction *Inst, const Value *Ptr,
  86                            ProvenanceAnalysis &PA, ARCInstKind Class) {
  87   // ARCInstKind::Call operations (as opposed to
  88   // ARCInstKind::CallOrUser) never "use" objc pointers.
  89   if (Class == ARCInstKind::Call)
  90     return false;
  91
  92   const DataLayout &DL = Inst->getModule()->getDataLayout();
  93
  94   // Consider various instructions which may have pointer arguments which are
  95   // not "uses".
  96   if (const ICmpInst *ICI = dyn_cast<ICmpInst>(Inst)) {
  97     // Comparing a pointer with null, or any other constant, isn't really a use,
  98     // because we don't care what the pointer points to, or about the values
  99     // of any other dynamic reference-counted pointers.
 100     if (!IsPotentialRetainableObjPtr(ICI->getOperand(1), *PA.getAA()))
 101       return false;
 102   } else if (auto CS = ImmutableCallSite(Inst)) {
 103     // For calls, just check the arguments (and not the callee operand).
 104     for (ImmutableCallSite::arg_iterator OI = CS.arg_begin(),
 105          OE = CS.arg_end(); OI != OE; ++OI) {
 106       const Value *Op = *OI;
 107       if (IsPotentialRetainableObjPtr(Op, *PA.getAA()) &&
 108           PA.related(Ptr, Op, DL))
 109         return true;
 110     }
 111     return false;
 112   } else if (const StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
 113     // Special-case stores, because we don't care about the stored value, just
 114     // the store address.
 115     const Value *Op = GetUnderlyingObjCPtr(SI->getPointerOperand(), DL);
 116     // If we can't tell what the underlying object was, assume there is a
 117     // dependence.
 118     return IsPotentialRetainableObjPtr(Op, *PA.getAA()) &&
 119            PA.related(Op, Ptr, DL);
 120   }
 121
 122   // Check each operand for a match.
 123   for (User::const_op_iterator OI = Inst->op_begin(), OE = Inst->op_end();
 124        OI != OE; ++OI) {
 125     const Value *Op = *OI;
 126     if (IsPotentialRetainableObjPtr(Op, *PA.getAA()) && PA.related(Ptr, Op, DL))
 127       return true;
 128   }
 129   return false;
 130 }
 131
 132 /// Test if there can be dependencies on Inst through Arg. This function only
 133 /// tests dependencies relevant for removing pairs of calls.
 134 bool
 135 llvm::objcarc::Depends(DependenceKind Flavor, Instruction *Inst,
 136                        const Value *Arg, ProvenanceAnalysis &PA) {
 137   // If we've reached the definition of Arg, stop.
 138   if (Inst == Arg)
 139     return true;
 140
 141   switch (Flavor) {
 142   case NeedsPositiveRetainCount: {
 143     ARCInstKind Class = GetARCInstKind(Inst);
 144     switch (Class) {
 145     case ARCInstKind::AutoreleasepoolPop:
 146     case ARCInstKind::AutoreleasepoolPush:
 147     case ARCInstKind::None:
 148       return false;
 149     default:
 150       return CanUse(Inst, Arg, PA, Class);
 151     }
 152   }
 153
 154   case AutoreleasePoolBoundary: {
 155     ARCInstKind Class = GetARCInstKind(Inst);
 156     switch (Class) {
 157     case ARCInstKind::AutoreleasepoolPop:
 158     case ARCInstKind::AutoreleasepoolPush:
 159       // These mark the end and begin of an autorelease pool scope.
 160       return true;
 161     default:
 162       // Nothing else does this.
 163       return false;
 164     }
 165   }
 166
 167   case CanChangeRetainCount: {
 168     ARCInstKind Class = GetARCInstKind(Inst);
 169     switch (Class) {
 170     case ARCInstKind::AutoreleasepoolPop:
 171       // Conservatively assume this can decrement any count.
 172       return true;
 173     case ARCInstKind::AutoreleasepoolPush:
 174     case ARCInstKind::None:
 175       return false;
 176     default:
 177       return CanAlterRefCount(Inst, Arg, PA, Class);
 178     }
 179   }
 180
 181   case RetainAutoreleaseDep:
 182     switch (GetBasicARCInstKind(Inst)) {
 183     case ARCInstKind::AutoreleasepoolPop:
 184     case ARCInstKind::AutoreleasepoolPush:
 185       // Don't merge an objc_autorelease with an objc_retain inside a different
 186       // autoreleasepool scope.
 187       return true;
 188     case ARCInstKind::Retain:
 189     case ARCInstKind::RetainRV:
 190       // Check for a retain of the same pointer for merging.
 191       return GetArgRCIdentityRoot(Inst) == Arg;
 192     default:
 193       // Nothing else matters for objc_retainAutorelease formation.
 194       return false;
 195     }
 196
 197   case RetainAutoreleaseRVDep: {
 198     ARCInstKind Class = GetBasicARCInstKind(Inst);
 199     switch (Class) {
 200     case ARCInstKind::Retain:
 201     case ARCInstKind::RetainRV:
 202       // Check for a retain of the same pointer for merging.
 203       return GetArgRCIdentityRoot(Inst) == Arg;
 204     default:
 205       // Anything that can autorelease interrupts
 206       // retainAutoreleaseReturnValue formation.
 207       return CanInterruptRV(Class);
 208     }
 209   }
 210
 211   case RetainRVDep:
 212     return CanInterruptRV(GetBasicARCInstKind(Inst));
 213   }
 214
 215   llvm_unreachable("Invalid dependence flavor");
 216 }
 217
 218 /// Walk up the CFG from StartPos (which is in StartBB) and find local and
 219 /// non-local dependencies on Arg.
 220 ///
 221 /// TODO: Cache results?
 222 void
 223 llvm::objcarc::FindDependencies(DependenceKind Flavor,
 224                                 const Value *Arg,
 225                                 BasicBlock *StartBB, Instruction *StartInst,
 226                                 SmallPtrSetImpl<Instruction *> &DependingInsts,
 227                                 SmallPtrSetImpl<const BasicBlock *> &Visited,
 228                                 ProvenanceAnalysis &PA) {
 229   BasicBlock::iterator StartPos = StartInst;
 230
 231   SmallVector<std::pair<BasicBlock *, BasicBlock::iterator>, 4> Worklist;
 232   Worklist.push_back(std::make_pair(StartBB, StartPos));
 233   do {
 234     std::pair<BasicBlock *, BasicBlock::iterator> Pair =
 235       Worklist.pop_back_val();
 236     BasicBlock *LocalStartBB = Pair.first;
 237     BasicBlock::iterator LocalStartPos = Pair.second;
 238     BasicBlock::iterator StartBBBegin = LocalStartBB->begin();
 239     for (;;) {
 240       if (LocalStartPos == StartBBBegin) {
 241         pred_iterator PI(LocalStartBB), PE(LocalStartBB, false);
 242         if (PI == PE)
 243           // If we've reached the function entry, produce a null dependence.
 244           DependingInsts.insert(nullptr);
 245         else
 246           // Add the predecessors to the worklist.
 247           do {
 248             BasicBlock *PredBB = *PI;
 249             if (Visited.insert(PredBB).second)
 250               Worklist.push_back(std::make_pair(PredBB, PredBB->end()));
 251           } while (++PI != PE);
 252         break;
 253       }
 254
 255       Instruction *Inst = --LocalStartPos;
 256       if (Depends(Flavor, Inst, Arg, PA)) {
 257         DependingInsts.insert(Inst);
 258         break;
 259       }
 260     }
 261   } while (!Worklist.empty());
 262
 263   // Determine whether the original StartBB post-dominates all of the blocks we
 264   // visited. If not, insert a sentinal indicating that most optimizations are
 265   // not safe.
 266   for (const BasicBlock *BB : Visited) {
 267     if (BB == StartBB)
 268       continue;
 269     const TerminatorInst *TI = cast<TerminatorInst>(&BB->back());
 270     for (succ_const_iterator SI(TI), SE(TI, false); SI != SE; ++SI) {
 271       const BasicBlock *Succ = *SI;
 272       if (Succ != StartBB && !Visited.count(Succ)) {
 273         DependingInsts.insert(reinterpret_cast<Instruction *>(-1));
 274         return;
 275       }
 276     }
 277   }
 278 }