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