lib/Transforms/ObjCARC/DependencyAnalysis.cpp

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