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