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
  36 llvm::objcarc::CanAlterRefCount(const Instruction *Inst, const Value *Ptr,
  37                                 ProvenanceAnalysis &PA,
  38                                 InstructionClass Class) {
  39   switch (Class) {
  40   case IC_Autorelease:
  41   case IC_AutoreleaseRV:
  42   case IC_IntrinsicUser:
  43   case IC_User:
  44     // These operations never directly modify a reference count.
  45     return false;
  46   default: break;
  47   }
  48
  49   ImmutableCallSite CS = static_cast<const Value *>(Inst);
  50   assert(CS && "Only calls can alter reference counts!");
  51
  52   // See if AliasAnalysis can help us with the call.
  53   AliasAnalysis::ModRefBehavior MRB = PA.getAA()->getModRefBehavior(CS);
  54   if (AliasAnalysis::onlyReadsMemory(MRB))
  55     return false;
  56   if (AliasAnalysis::onlyAccessesArgPointees(MRB)) {
  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()) && PA.related(Ptr, Op))
  61         return true;
  62     }
  63     return false;
  64   }
  65
  66   // Assume the worst.
  67   return true;
  68 }
  69
  70 /// Test whether the given instruction can "use" the given pointer's object in a
  71 /// way that requires the reference count to be positive.
  72 bool
  73 llvm::objcarc::CanUse(const Instruction *Inst, const Value *Ptr,
  74                       ProvenanceAnalysis &PA, InstructionClass Class) {
  75   // IC_Call operations (as opposed to IC_CallOrUser) never "use" objc pointers.
  76   if (Class == IC_Call)
  77     return false;
  78
  79   // Consider various instructions which may have pointer arguments which are
  80   // not "uses".
  81   if (const ICmpInst *ICI = dyn_cast<ICmpInst>(Inst)) {
  82     // Comparing a pointer with null, or any other constant, isn't really a use,
  83     // because we don't care what the pointer points to, or about the values
  84     // of any other dynamic reference-counted pointers.
  85     if (!IsPotentialRetainableObjPtr(ICI->getOperand(1), *PA.getAA()))
  86       return false;
  87   } else if (ImmutableCallSite CS = static_cast<const Value *>(Inst)) {
  88     // For calls, just check the arguments (and not the callee operand).
  89     for (ImmutableCallSite::arg_iterator OI = CS.arg_begin(),
  90          OE = CS.arg_end(); OI != OE; ++OI) {
  91       const Value *Op = *OI;
  92       if (IsPotentialRetainableObjPtr(Op, *PA.getAA()) && PA.related(Ptr, Op))
  93         return true;
  94     }
  95     return false;
  96   } else if (const StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
  97     // Special-case stores, because we don't care about the stored value, just
  98     // the store address.
  99     const Value *Op = GetUnderlyingObjCPtr(SI->getPointerOperand());
 100     // If we can't tell what the underlying object was, assume there is a
 101     // dependence.
 102     return IsPotentialRetainableObjPtr(Op, *PA.getAA()) && PA.related(Op, Ptr);
 103   }
 104
 105   // Check each operand for a match.
 106   for (User::const_op_iterator OI = Inst->op_begin(), OE = Inst->op_end();
 107        OI != OE; ++OI) {
 108     const Value *Op = *OI;
 109     if (IsPotentialRetainableObjPtr(Op, *PA.getAA()) && PA.related(Ptr, Op))
 110       return true;
 111   }
 112   return false;
 113 }
 114
 115 /// Test if there can be dependencies on Inst through Arg. This function only
 116 /// tests dependencies relevant for removing pairs of calls.
 117 bool
 118 llvm::objcarc::Depends(DependenceKind Flavor, Instruction *Inst,
 119                        const Value *Arg, ProvenanceAnalysis &PA) {
 120   // If we've reached the definition of Arg, stop.
 121   if (Inst == Arg)
 122     return true;
 123
 124   switch (Flavor) {
 125   case NeedsPositiveRetainCount: {
 126     InstructionClass Class = GetInstructionClass(Inst);
 127     switch (Class) {
 128     case IC_AutoreleasepoolPop:
 129     case IC_AutoreleasepoolPush:
 130     case IC_None:
 131       return false;
 132     default:
 133       return CanUse(Inst, Arg, PA, Class);
 134     }
 135   }
 136
 137   case AutoreleasePoolBoundary: {
 138     InstructionClass Class = GetInstructionClass(Inst);
 139     switch (Class) {
 140     case IC_AutoreleasepoolPop:
 141     case IC_AutoreleasepoolPush:
 142       // These mark the end and begin of an autorelease pool scope.
 143       return true;
 144     default:
 145       // Nothing else does this.
 146       return false;
 147     }
 148   }
 149
 150   case CanChangeRetainCount: {
 151     InstructionClass Class = GetInstructionClass(Inst);
 152     switch (Class) {
 153     case IC_AutoreleasepoolPop:
 154       // Conservatively assume this can decrement any count.
 155       return true;
 156     case IC_AutoreleasepoolPush:
 157     case IC_None:
 158       return false;
 159     default:
 160       return CanAlterRefCount(Inst, Arg, PA, Class);
 161     }
 162   }
 163
 164   case RetainAutoreleaseDep:
 165     switch (GetBasicInstructionClass(Inst)) {
 166     case IC_AutoreleasepoolPop:
 167     case IC_AutoreleasepoolPush:
 168       // Don't merge an objc_autorelease with an objc_retain inside a different
 169       // autoreleasepool scope.
 170       return true;
 171     case IC_Retain:
 172     case IC_RetainRV:
 173       // Check for a retain of the same pointer for merging.
 174       return GetObjCArg(Inst) == Arg;
 175     default:
 176       // Nothing else matters for objc_retainAutorelease formation.
 177       return false;
 178     }
 179
 180   case RetainAutoreleaseRVDep: {
 181     InstructionClass Class = GetBasicInstructionClass(Inst);
 182     switch (Class) {
 183     case IC_Retain:
 184     case IC_RetainRV:
 185       // Check for a retain of the same pointer for merging.
 186       return GetObjCArg(Inst) == Arg;
 187     default:
 188       // Anything that can autorelease interrupts
 189       // retainAutoreleaseReturnValue formation.
 190       return CanInterruptRV(Class);
 191     }
 192   }
 193
 194   case RetainRVDep:
 195     return CanInterruptRV(GetBasicInstructionClass(Inst));
 196   }
 197
 198   llvm_unreachable("Invalid dependence flavor");
 199 }
 200
 201 /// Walk up the CFG from StartPos (which is in StartBB) and find local and
 202 /// non-local dependencies on Arg.
 203 ///
 204 /// TODO: Cache results?
 205 void
 206 llvm::objcarc::FindDependencies(DependenceKind Flavor,
 207                                 const Value *Arg,
 208                                 BasicBlock *StartBB, Instruction *StartInst,
 209                                 SmallPtrSet<Instruction *, 4> &DependingInsts,
 210                                 SmallPtrSet<const BasicBlock *, 4> &Visited,
 211                                 ProvenanceAnalysis &PA) {
 212   BasicBlock::iterator StartPos = StartInst;
 213
 214   SmallVector<std::pair<BasicBlock *, BasicBlock::iterator>, 4> Worklist;
 215   Worklist.push_back(std::make_pair(StartBB, StartPos));
 216   do {
 217     std::pair<BasicBlock *, BasicBlock::iterator> Pair =
 218       Worklist.pop_back_val();
 219     BasicBlock *LocalStartBB = Pair.first;
 220     BasicBlock::iterator LocalStartPos = Pair.second;
 221     BasicBlock::iterator StartBBBegin = LocalStartBB->begin();
 222     for (;;) {
 223       if (LocalStartPos == StartBBBegin) {
 224         pred_iterator PI(LocalStartBB), PE(LocalStartBB, false);
 225         if (PI == PE)
 226           // If we've reached the function entry, produce a null dependence.
 227           DependingInsts.insert(nullptr);
 228         else
 229           // Add the predecessors to the worklist.
 230           do {
 231             BasicBlock *PredBB = *PI;
 232             if (Visited.insert(PredBB))
 233               Worklist.push_back(std::make_pair(PredBB, PredBB->end()));
 234           } while (++PI != PE);
 235         break;
 236       }
 237
 238       Instruction *Inst = --LocalStartPos;
 239       if (Depends(Flavor, Inst, Arg, PA)) {
 240         DependingInsts.insert(Inst);
 241         break;
 242       }
 243     }
 244   } while (!Worklist.empty());
 245
 246   // Determine whether the original StartBB post-dominates all of the blocks we
 247   // visited. If not, insert a sentinal indicating that most optimizations are
 248   // not safe.
 249   for (SmallPtrSet<const BasicBlock *, 4>::const_iterator I = Visited.begin(),
 250        E = Visited.end(); I != E; ++I) {
 251     const BasicBlock *BB = *I;
 252     if (BB == StartBB)
 253       continue;
 254     const TerminatorInst *TI = cast<TerminatorInst>(&BB->back());
 255     for (succ_const_iterator SI(TI), SE(TI, false); SI != SE; ++SI) {
 256       const BasicBlock *Succ = *SI;
 257       if (Succ != StartBB && !Visited.count(Succ)) {
 258         DependingInsts.insert(reinterpret_cast<Instruction *>(-1));
 259         return;
 260       }
 261     }
 262   }
 263 }