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