LLVM  mainline
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 llvm::objcarc::CanAlterRefCount(const Instruction *Inst, const Value *Ptr,
00036                                      ProvenanceAnalysis &PA,
00037                                      ARCInstKind Class) {
00038   switch (Class) {
00039   case ARCInstKind::Autorelease:
00040   case ARCInstKind::AutoreleaseRV:
00041   case ARCInstKind::IntrinsicUser:
00042   case ARCInstKind::User:
00043     // These operations never directly modify a reference count.
00044     return false;
00045   default: break;
00046   }
00047 
00048   ImmutableCallSite CS(Inst);
00049   assert(CS && "Only calls can alter reference counts!");
00050 
00051   // See if AliasAnalysis can help us with the call.
00052   AliasAnalysis::ModRefBehavior MRB = PA.getAA()->getModRefBehavior(CS);
00053   if (AliasAnalysis::onlyReadsMemory(MRB))
00054     return false;
00055   if (AliasAnalysis::onlyAccessesArgPointees(MRB)) {
00056     const DataLayout &DL = Inst->getModule()->getDataLayout();
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()) &&
00061           PA.related(Ptr, Op, DL))
00062         return true;
00063     }
00064     return false;
00065   }
00066 
00067   // Assume the worst.
00068   return true;
00069 }
00070 
00071 bool llvm::objcarc::CanDecrementRefCount(const Instruction *Inst,
00072                                          const Value *Ptr,
00073                                          ProvenanceAnalysis &PA,
00074                                          ARCInstKind Class) {
00075   // First perform a quick check if Class can not touch ref counts.
00076   if (!CanDecrementRefCount(Class))
00077     return false;
00078 
00079   // Otherwise, just use CanAlterRefCount for now.
00080   return CanAlterRefCount(Inst, Ptr, PA, Class);
00081 }
00082 
00083 /// Test whether the given instruction can "use" the given pointer's object in a
00084 /// way that requires the reference count to be positive.
00085 bool llvm::objcarc::CanUse(const Instruction *Inst, const Value *Ptr,
00086                            ProvenanceAnalysis &PA, ARCInstKind Class) {
00087   // ARCInstKind::Call operations (as opposed to
00088   // ARCInstKind::CallOrUser) never "use" objc pointers.
00089   if (Class == ARCInstKind::Call)
00090     return false;
00091 
00092   const DataLayout &DL = Inst->getModule()->getDataLayout();
00093 
00094   // Consider various instructions which may have pointer arguments which are
00095   // not "uses".
00096   if (const ICmpInst *ICI = dyn_cast<ICmpInst>(Inst)) {
00097     // Comparing a pointer with null, or any other constant, isn't really a use,
00098     // because we don't care what the pointer points to, or about the values
00099     // of any other dynamic reference-counted pointers.
00100     if (!IsPotentialRetainableObjPtr(ICI->getOperand(1), *PA.getAA()))
00101       return false;
00102   } else if (auto CS = ImmutableCallSite(Inst)) {
00103     // For calls, just check the arguments (and not the callee operand).
00104     for (ImmutableCallSite::arg_iterator OI = CS.arg_begin(),
00105          OE = CS.arg_end(); OI != OE; ++OI) {
00106       const Value *Op = *OI;
00107       if (IsPotentialRetainableObjPtr(Op, *PA.getAA()) &&
00108           PA.related(Ptr, Op, DL))
00109         return true;
00110     }
00111     return false;
00112   } else if (const StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
00113     // Special-case stores, because we don't care about the stored value, just
00114     // the store address.
00115     const Value *Op = GetUnderlyingObjCPtr(SI->getPointerOperand(), DL);
00116     // If we can't tell what the underlying object was, assume there is a
00117     // dependence.
00118     return IsPotentialRetainableObjPtr(Op, *PA.getAA()) &&
00119            PA.related(Op, Ptr, DL);
00120   }
00121 
00122   // Check each operand for a match.
00123   for (User::const_op_iterator OI = Inst->op_begin(), OE = Inst->op_end();
00124        OI != OE; ++OI) {
00125     const Value *Op = *OI;
00126     if (IsPotentialRetainableObjPtr(Op, *PA.getAA()) && PA.related(Ptr, Op, DL))
00127       return true;
00128   }
00129   return false;
00130 }
00131 
00132 /// Test if there can be dependencies on Inst through Arg. This function only
00133 /// tests dependencies relevant for removing pairs of calls.
00134 bool
00135 llvm::objcarc::Depends(DependenceKind Flavor, Instruction *Inst,
00136                        const Value *Arg, ProvenanceAnalysis &PA) {
00137   // If we've reached the definition of Arg, stop.
00138   if (Inst == Arg)
00139     return true;
00140 
00141   switch (Flavor) {
00142   case NeedsPositiveRetainCount: {
00143     ARCInstKind Class = GetARCInstKind(Inst);
00144     switch (Class) {
00145     case ARCInstKind::AutoreleasepoolPop:
00146     case ARCInstKind::AutoreleasepoolPush:
00147     case ARCInstKind::None:
00148       return false;
00149     default:
00150       return CanUse(Inst, Arg, PA, Class);
00151     }
00152   }
00153 
00154   case AutoreleasePoolBoundary: {
00155     ARCInstKind Class = GetARCInstKind(Inst);
00156     switch (Class) {
00157     case ARCInstKind::AutoreleasepoolPop:
00158     case ARCInstKind::AutoreleasepoolPush:
00159       // These mark the end and begin of an autorelease pool scope.
00160       return true;
00161     default:
00162       // Nothing else does this.
00163       return false;
00164     }
00165   }
00166 
00167   case CanChangeRetainCount: {
00168     ARCInstKind Class = GetARCInstKind(Inst);
00169     switch (Class) {
00170     case ARCInstKind::AutoreleasepoolPop:
00171       // Conservatively assume this can decrement any count.
00172       return true;
00173     case ARCInstKind::AutoreleasepoolPush:
00174     case ARCInstKind::None:
00175       return false;
00176     default:
00177       return CanAlterRefCount(Inst, Arg, PA, Class);
00178     }
00179   }
00180 
00181   case RetainAutoreleaseDep:
00182     switch (GetBasicARCInstKind(Inst)) {
00183     case ARCInstKind::AutoreleasepoolPop:
00184     case ARCInstKind::AutoreleasepoolPush:
00185       // Don't merge an objc_autorelease with an objc_retain inside a different
00186       // autoreleasepool scope.
00187       return true;
00188     case ARCInstKind::Retain:
00189     case ARCInstKind::RetainRV:
00190       // Check for a retain of the same pointer for merging.
00191       return GetArgRCIdentityRoot(Inst) == Arg;
00192     default:
00193       // Nothing else matters for objc_retainAutorelease formation.
00194       return false;
00195     }
00196 
00197   case RetainAutoreleaseRVDep: {
00198     ARCInstKind Class = GetBasicARCInstKind(Inst);
00199     switch (Class) {
00200     case ARCInstKind::Retain:
00201     case ARCInstKind::RetainRV:
00202       // Check for a retain of the same pointer for merging.
00203       return GetArgRCIdentityRoot(Inst) == Arg;
00204     default:
00205       // Anything that can autorelease interrupts
00206       // retainAutoreleaseReturnValue formation.
00207       return CanInterruptRV(Class);
00208     }
00209   }
00210 
00211   case RetainRVDep:
00212     return CanInterruptRV(GetBasicARCInstKind(Inst));
00213   }
00214 
00215   llvm_unreachable("Invalid dependence flavor");
00216 }
00217 
00218 /// Walk up the CFG from StartPos (which is in StartBB) and find local and
00219 /// non-local dependencies on Arg.
00220 ///
00221 /// TODO: Cache results?
00222 void
00223 llvm::objcarc::FindDependencies(DependenceKind Flavor,
00224                                 const Value *Arg,
00225                                 BasicBlock *StartBB, Instruction *StartInst,
00226                                 SmallPtrSetImpl<Instruction *> &DependingInsts,
00227                                 SmallPtrSetImpl<const BasicBlock *> &Visited,
00228                                 ProvenanceAnalysis &PA) {
00229   BasicBlock::iterator StartPos = StartInst;
00230 
00231   SmallVector<std::pair<BasicBlock *, BasicBlock::iterator>, 4> Worklist;
00232   Worklist.push_back(std::make_pair(StartBB, StartPos));
00233   do {
00234     std::pair<BasicBlock *, BasicBlock::iterator> Pair =
00235       Worklist.pop_back_val();
00236     BasicBlock *LocalStartBB = Pair.first;
00237     BasicBlock::iterator LocalStartPos = Pair.second;
00238     BasicBlock::iterator StartBBBegin = LocalStartBB->begin();
00239     for (;;) {
00240       if (LocalStartPos == StartBBBegin) {
00241         pred_iterator PI(LocalStartBB), PE(LocalStartBB, false);
00242         if (PI == PE)
00243           // If we've reached the function entry, produce a null dependence.
00244           DependingInsts.insert(nullptr);
00245         else
00246           // Add the predecessors to the worklist.
00247           do {
00248             BasicBlock *PredBB = *PI;
00249             if (Visited.insert(PredBB).second)
00250               Worklist.push_back(std::make_pair(PredBB, PredBB->end()));
00251           } while (++PI != PE);
00252         break;
00253       }
00254 
00255       Instruction *Inst = --LocalStartPos;
00256       if (Depends(Flavor, Inst, Arg, PA)) {
00257         DependingInsts.insert(Inst);
00258         break;
00259       }
00260     }
00261   } while (!Worklist.empty());
00262 
00263   // Determine whether the original StartBB post-dominates all of the blocks we
00264   // visited. If not, insert a sentinal indicating that most optimizations are
00265   // not safe.
00266   for (const BasicBlock *BB : Visited) {
00267     if (BB == StartBB)
00268       continue;
00269     const TerminatorInst *TI = cast<TerminatorInst>(&BB->back());
00270     for (succ_const_iterator SI(TI), SE(TI, false); SI != SE; ++SI) {
00271       const BasicBlock *Succ = *SI;
00272       if (Succ != StartBB && !Visited.count(Succ)) {
00273         DependingInsts.insert(reinterpret_cast<Instruction *>(-1));
00274         return;
00275       }
00276     }
00277   }
00278 }