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 } 262