ObjCARC.cpp

//===- ObjCARC.cpp - ObjC ARC Optimization --------------------------------===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This file defines ObjC ARC optimizations. ARC stands for
// Automatic Reference Counting and is a system for managing reference counts
// for objects in Objective C.
//
// The optimizations performed include elimination of redundant, partially
// redundant, and inconsequential reference count operations, elimination of
// redundant weak pointer operations, pattern-matching and replacement of
// low-level operations into higher-level operations, and numerous minor
// simplifications.
//
// This file also defines a simple ARC-aware AliasAnalysis.
//
// WARNING: This file knows about certain library functions. It recognizes them
// by name, and hardwires knowedge of their semantics.
//
// WARNING: This file knows about how certain Objective-C library functions are
// used. Naive LLVM IR transformations which would otherwise be
// behavior-preserving may break these assumptions.
//
//===----------------------------------------------------------------------===//

#define DEBUG_TYPE "objc-arc"
#include "llvm/Function.h"
#include "llvm/Intrinsics.h"
#include "llvm/GlobalVariable.h"
#include "llvm/DerivedTypes.h"
#include "llvm/Module.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/Transforms/Utils/Local.h"
#include "llvm/Support/CallSite.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/ADT/StringSwitch.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/STLExtras.h"
using namespace llvm;

// A handy option to enable/disable all optimizations in this file.
static cl::opt<bool> EnableARCOpts("enable-objc-arc-opts", cl::init(true));

//===----------------------------------------------------------------------===//
// Misc. Utilities
//===----------------------------------------------------------------------===//

namespace {
  /// MapVector - An associative container with fast insertion-order
  /// (deterministic) iteration over its elements. Plus the special
  /// blot operation.
  template<class KeyT, class ValueT>
  class MapVector {
    /// Map - Map keys to indices in Vector.
    typedef DenseMap<KeyT, size_t> MapTy;
    MapTy Map;

    /// Vector - Keys and values.
    typedef std::vector<std::pair<KeyT, ValueT> > VectorTy;
    VectorTy Vector;

  public:
    typedef typename VectorTy::iterator iterator;
    typedef typename VectorTy::const_iterator const_iterator;
    iterator begin() { return Vector.begin(); }
    iterator end() { return Vector.end(); }
    const_iterator begin() const { return Vector.begin(); }
    const_iterator end() const { return Vector.end(); }

#ifdef XDEBUG
    ~MapVector() {
      assert(Vector.size() >= Map.size()); // May differ due to blotting.
      for (typename MapTy::const_iterator I = Map.begin(), E = Map.end();
           I != E; ++I) {
        assert(I->second < Vector.size());
        assert(Vector[I->second].first == I->first);
      }
      for (typename VectorTy::const_iterator I = Vector.begin(),
           E = Vector.end(); I != E; ++I)
        assert(!I->first ||
               (Map.count(I->first) &&
                Map[I->first] == size_t(I - Vector.begin())));
    }
#endif

    ValueT &operator[](KeyT Arg) {
      std::pair<typename MapTy::iterator, bool> Pair =
        Map.insert(std::make_pair(Arg, size_t(0)));
      if (Pair.second) {
        Pair.first->second = Vector.size();
        Vector.push_back(std::make_pair(Arg, ValueT()));
        return Vector.back().second;
      }
      return Vector[Pair.first->second].second;
    }

    std::pair<iterator, bool>
    insert(const std::pair<KeyT, ValueT> &InsertPair) {
      std::pair<typename MapTy::iterator, bool> Pair =
        Map.insert(std::make_pair(InsertPair.first, size_t(0)));
      if (Pair.second) {
        Pair.first->second = Vector.size();
        Vector.push_back(InsertPair);
        return std::make_pair(llvm::prior(Vector.end()), true);
      }
      return std::make_pair(Vector.begin() + Pair.first->second, false);
    }

    const_iterator find(KeyT Key) const {
      typename MapTy::const_iterator It = Map.find(Key);
      if (It == Map.end()) return Vector.end();
      return Vector.begin() + It->second;
    }

    /// blot - This is similar to erase, but instead of removing the element
    /// from the vector, it just zeros out the key in the vector. This leaves
    /// iterators intact, but clients must be prepared for zeroed-out keys when
    /// iterating.
    void blot(KeyT Key) {
      typename MapTy::iterator It = Map.find(Key);
      if (It == Map.end()) return;
      Vector[It->second].first = KeyT();
      Map.erase(It);
    }

    void clear() {
      Map.clear();
      Vector.clear();
    }
  };
}

//===----------------------------------------------------------------------===//
// ARC Utilities.
//===----------------------------------------------------------------------===//

namespace {
  /// InstructionClass - A simple classification for instructions.
  enum InstructionClass {
    IC_Retain,              ///< objc_retain
    IC_RetainRV,            ///< objc_retainAutoreleasedReturnValue
    IC_RetainBlock,         ///< objc_retainBlock
    IC_Release,             ///< objc_release
    IC_Autorelease,         ///< objc_autorelease
    IC_AutoreleaseRV,       ///< objc_autoreleaseReturnValue
    IC_AutoreleasepoolPush, ///< objc_autoreleasePoolPush
    IC_AutoreleasepoolPop,  ///< objc_autoreleasePoolPop
    IC_NoopCast,            ///< objc_retainedObject, etc.
    IC_FusedRetainAutorelease, ///< objc_retainAutorelease
    IC_FusedRetainAutoreleaseRV, ///< objc_retainAutoreleaseReturnValue
    IC_LoadWeakRetained,    ///< objc_loadWeakRetained (primitive)
    IC_StoreWeak,           ///< objc_storeWeak (primitive)
    IC_InitWeak,            ///< objc_initWeak (derived)
    IC_LoadWeak,            ///< objc_loadWeak (derived)
    IC_MoveWeak,            ///< objc_moveWeak (derived)
    IC_CopyWeak,            ///< objc_copyWeak (derived)
    IC_DestroyWeak,         ///< objc_destroyWeak (derived)
    IC_CallOrUser,          ///< could call objc_release and/or "use" pointers
    IC_Call,                ///< could call objc_release
    IC_User,                ///< could "use" a pointer
    IC_None                 ///< anything else
  };
}

/// IsPotentialUse - Test whether the given value is possible a
/// reference-counted pointer.
static bool IsPotentialUse(const Value *Op) {
  // Pointers to static or stack storage are not reference-counted pointers.
  if (isa<Constant>(Op) || isa<AllocaInst>(Op))
    return false;
  // Special arguments are not reference-counted.
  if (const Argument *Arg = dyn_cast<Argument>(Op))
    if (Arg->hasByValAttr() ||
        Arg->hasNestAttr() ||
        Arg->hasStructRetAttr())
      return false;
  // Only consider values with pointer types, and not function pointers.
  PointerType *Ty = dyn_cast<PointerType>(Op->getType());
  if (!Ty || isa<FunctionType>(Ty->getElementType()))
    return false;
  // Conservatively assume anything else is a potential use.
  return true;
}

/// GetCallSiteClass - Helper for GetInstructionClass. Determines what kind
/// of construct CS is.
static InstructionClass GetCallSiteClass(ImmutableCallSite CS) {
  for (ImmutableCallSite::arg_iterator I = CS.arg_begin(), E = CS.arg_end();
       I != E; ++I)
    if (IsPotentialUse(*I))
      return CS.onlyReadsMemory() ? IC_User : IC_CallOrUser;

  return CS.onlyReadsMemory() ? IC_None : IC_Call;
}