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