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