LLVM API Documentation

DependencyAnalysis.cpp
Go to the documentation of this file.
00001 //===- DependencyAnalysis.cpp - ObjC ARC Optimization ---------------------===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 /// \file
00010 ///
00011 /// This file defines special dependency analysis routines used in Objective C
00012 /// ARC Optimizations.
00013 ///
00014 /// WARNING: This file knows about certain library functions. It recognizes them
00015 /// by name, and hardwires knowledge of their semantics.
00016 ///
00017 /// WARNING: This file knows about how certain Objective-C library functions are
00018 /// used. Naive LLVM IR transformations which would otherwise be
00019 /// behavior-preserving may break these assumptions.
00020 ///
00021 //===----------------------------------------------------------------------===//
00022 
00023 #include "ObjCARC.h"
00024 #include "DependencyAnalysis.h"
00025 #include "ProvenanceAnalysis.h"
00026 #include "llvm/IR/CFG.h"
00027 
00028 using namespace llvm;
00029 using namespace llvm::objcarc;
00030 
00031 #define DEBUG_TYPE "objc-arc-dependency"
00032 
00033 /// Test whether the given instruction can result in a reference count
00034 /// modification (positive or negative) for the pointer's object.
00035 bool
00036 llvm::objcarc::CanAlterRefCount(const Instruction *Inst, const Value *Ptr,
00037                                 ProvenanceAnalysis &PA,
00038                                 InstructionClass Class) {
00039   switch (Class) {
00040   case IC_Autorelease:
00041   case IC_AutoreleaseRV:
00042   case IC_IntrinsicUser:
00043   case IC_User:
00044     // These operations never directly modify a reference count.
00045     return false;
00046   default: break;
00047   }
00048 
00049   ImmutableCallSite CS = static_cast<const Value *>(Inst);
00050   assert(CS && "Only calls can alter reference counts!");
00051 
00052   // See if AliasAnalysis can help us with the call.
00053   AliasAnalysis::ModRefBehavior MRB = PA.getAA()->getModRefBehavior(CS);
00054   if (AliasAnalysis::onlyReadsMemory(MRB))
00055     return false;
00056   if (AliasAnalysis::onlyAccessesArgPointees(MRB)) {
00057     for (ImmutableCallSite::arg_iterator I = CS.arg_begin(), E = CS.arg_end();
00058          I != E; ++I) {
00059       const Value *Op = *I;
00060       if (IsPotentialRetainableObjPtr(Op, *PA.getAA()) && PA.related(Ptr, Op))
00061         return true;
00062     }
00063     return false;
00064   }
00065 
00066   // Assume the worst.
00067   return true;
00068 }
00069 
00070 /// Test whether the given instruction can "use" the given pointer's object in a
00071 /// way that requires the reference count to be positive.
00072 bool
00073 llvm::objcarc::CanUse(const Instruction *Inst, const Value *Ptr,
00074                       ProvenanceAnalysis &PA, InstructionClass Class) {
00075   // IC_Call operations (as opposed to IC_CallOrUser) never "use" objc pointers.
00076   if (Class == IC_Call)
00077     return false;
00078 
00079   // Consider various instructions which may have pointer arguments which are
00080   // not "uses".
00081   if (const ICmpInst *ICI = dyn_cast<ICmpInst>(Inst)) {
00082     // Comparing a pointer with null, or any other constant, isn't really a use,
00083     // because we don't care what the pointer points to, or about the values
00084     // of any other dynamic reference-counted pointers.
00085     if (!IsPotentialRetainableObjPtr(ICI->getOperand(1), *PA.getAA()))
00086       return false;
00087   } else if (ImmutableCallSite CS = static_cast<const Value *>(Inst)) {
00088     // For calls, just check the arguments (and not the callee operand).
00089     for (ImmutableCallSite::arg_iterator OI = CS.arg_begin(),
00090          OE = CS.arg_end(); OI != OE; ++OI) {
00091       const Value *Op = *OI;
00092       if (IsPotentialRetainableObjPtr(Op, *PA.getAA()) && PA.related(Ptr, Op))
00093         return true;
00094     }
00095     return false;
00096   } else if (const StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
00097     // Special-case stores, because we don't care about the stored value, just
00098     // the store address.
00099     const Value *Op = GetUnderlyingObjCPtr(SI->getPointerOperand());
00100     // If we can't tell what the underlying object was, assume there is a
00101     // dependence.
00102     return IsPotentialRetainableObjPtr(Op, *PA.getAA()) && PA.related(Op, Ptr);
00103   }
00104 
00105   // Check each operand for a match.
00106   for (User::const_op_iterator OI = Inst->op_begin(), OE = Inst->op_end();
00107        OI != OE; ++OI) {
00108     const Value *Op = *OI;
00109     if (IsPotentialRetainableObjPtr(Op, *PA.getAA()) && PA.related(Ptr, Op))
00110       return true;
00111   }
00112   return false;
00113 }
00114 
00115 /// Test if there can be dependencies on Inst through Arg. This function only
00116 /// tests dependencies relevant for removing pairs of calls.
00117 bool
00118 llvm::objcarc::Depends(DependenceKind Flavor, Instruction *Inst,
00119                        const Value *Arg, ProvenanceAnalysis &PA) {
00120   // If we've reached the definition of Arg, stop.
00121   if (Inst == Arg)
00122     return true;
00123 
00124   switch (Flavor) {
00125   case NeedsPositiveRetainCount: {
00126     InstructionClass Class = GetInstructionClass(Inst);
00127     switch (Class) {
00128     case IC_AutoreleasepoolPop:
00129     case IC_AutoreleasepoolPush:
00130     case IC_None:
00131       return false;
00132     default:
00133       return CanUse(Inst, Arg, PA, Class);
00134     }
00135   }
00136 
00137   case AutoreleasePoolBoundary: {
00138     InstructionClass Class = GetInstructionClass(Inst);
00139     switch (Class) {
00140     case IC_AutoreleasepoolPop:
00141     case IC_AutoreleasepoolPush:
00142       // These mark the end and begin of an autorelease pool scope.
00143       return true;
00144     default:
00145       // Nothing else does this.
00146       return false;
00147     }
00148   }
00149 
00150   case CanChangeRetainCount: {
00151     InstructionClass Class = GetInstructionClass(Inst);
00152     switch (Class) {
00153     case IC_AutoreleasepoolPop:
00154       // Conservatively assume this can decrement any count.
00155       return true;
00156     case IC_AutoreleasepoolPush:
00157     case IC_None:
00158       return false;
00159     default:
00160       return CanAlterRefCount(Inst, Arg, PA, Class);
00161     }
00162   }
00163 
00164   case RetainAutoreleaseDep:
00165     switch (GetBasicInstructionClass(Inst)) {
00166     case IC_AutoreleasepoolPop:
00167     case IC_AutoreleasepoolPush:
00168       // Don't merge an objc_autorelease with an objc_retain inside a different
00169       // autoreleasepool scope.
00170       return true;
00171     case IC_Retain:
00172     case IC_RetainRV:
00173       // Check for a retain of the same pointer for merging.
00174       return GetObjCArg(Inst) == Arg;
00175     default:
00176       // Nothing else matters for objc_retainAutorelease formation.
00177       return false;
00178     }
00179 
00180   case RetainAutoreleaseRVDep: {
00181     InstructionClass Class = GetBasicInstructionClass(Inst);
00182     switch (Class) {
00183     case IC_Retain:
00184     case IC_RetainRV:
00185       // Check for a retain of the same pointer for merging.
00186       return GetObjCArg(Inst) == Arg;
00187     default:
00188       // Anything that can autorelease interrupts
00189       // retainAutoreleaseReturnValue formation.
00190       return CanInterruptRV(Class);
00191     }
00192   }
00193 
00194   case RetainRVDep:
00195     return CanInterruptRV(GetBasicInstructionClass(Inst));
00196   }
00197 
00198   llvm_unreachable("Invalid dependence flavor");
00199 }
00200 
00201 /// Walk up the CFG from StartPos (which is in StartBB) and find local and
00202 /// non-local dependencies on Arg.
00203 ///
00204 /// TODO: Cache results?
00205 void
00206 llvm::objcarc::FindDependencies(DependenceKind Flavor,
00207                                 const Value *Arg,
00208                                 BasicBlock *StartBB, Instruction *StartInst,
00209                                 SmallPtrSet<Instruction *, 4> &DependingInsts,
00210                                 SmallPtrSet<const BasicBlock *, 4> &Visited,
00211                                 ProvenanceAnalysis &PA) {
00212   BasicBlock::iterator StartPos = StartInst;
00213 
00214   SmallVector<std::pair<BasicBlock *, BasicBlock::iterator>, 4> Worklist;
00215   Worklist.push_back(std::make_pair(StartBB, StartPos));
00216   do {
00217     std::pair<BasicBlock *, BasicBlock::iterator> Pair =
00218       Worklist.pop_back_val();
00219     BasicBlock *LocalStartBB = Pair.first;
00220     BasicBlock::iterator LocalStartPos = Pair.second;
00221     BasicBlock::iterator StartBBBegin = LocalStartBB->begin();
00222     for (;;) {
00223       if (LocalStartPos == StartBBBegin) {
00224         pred_iterator PI(LocalStartBB), PE(LocalStartBB, false);
00225         if (PI == PE)
00226           // If we've reached the function entry, produce a null dependence.
00227           DependingInsts.insert(nullptr);
00228         else
00229           // Add the predecessors to the worklist.
00230           do {
00231             BasicBlock *PredBB = *PI;
00232             if (Visited.insert(PredBB))
00233               Worklist.push_back(std::make_pair(PredBB, PredBB->end()));
00234           } while (++PI != PE);
00235         break;
00236       }
00237 
00238       Instruction *Inst = --LocalStartPos;
00239       if (Depends(Flavor, Inst, Arg, PA)) {
00240         DependingInsts.insert(Inst);
00241         break;
00242       }
00243     }
00244   } while (!Worklist.empty());
00245 
00246   // Determine whether the original StartBB post-dominates all of the blocks we
00247   // visited. If not, insert a sentinal indicating that most optimizations are
00248   // not safe.
00249   for (SmallPtrSet<const BasicBlock *, 4>::const_iterator I = Visited.begin(),
00250        E = Visited.end(); I != E; ++I) {
00251     const BasicBlock *BB = *I;
00252     if (BB == StartBB)
00253       continue;
00254     const TerminatorInst *TI = cast<TerminatorInst>(&BB->back());
00255     for (succ_const_iterator SI(TI), SE(TI, false); SI != SE; ++SI) {
00256       const BasicBlock *Succ = *SI;
00257       if (Succ != StartBB && !Visited.count(Succ)) {
00258         DependingInsts.insert(reinterpret_cast<Instruction *>(-1));
00259         return;
00260       }
00261     }
00262   }
00263 }