llvm/llvm/lib/Transforms/ObjCARC/ObjCARCOpts.cpp

//===- ObjCARCOpts.cpp - ObjC ARC Optimization ----------------------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
/// \file
/// 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, and numerous minor simplifications.
///
/// WARNING: This file knows about certain library functions. It recognizes them
/// by name, and hardwires knowledge 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.
//
//===----------------------------------------------------------------------===//

#include "ARCRuntimeEntryPoints.h"
#include "BlotMapVector.h"
#include "DependencyAnalysis.h"
#include "ObjCARC.h"
#include "ProvenanceAnalysis.h"
#include "PtrState.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/ObjCARCAliasAnalysis.h"
#include "llvm/Analysis/ObjCARCAnalysisUtils.h"
#include "llvm/Analysis/ObjCARCInstKind.h"
#include "llvm/Analysis/ObjCARCUtil.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/CFG.h"
#include "llvm/IR/Constant.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DerivedTypes.h"
#include "llvm/IR/EHPersonalities.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/GlobalVariable.h"
#include "llvm/IR/InstIterator.h"
#include "llvm/IR/InstrTypes.h"
#include "llvm/IR/Instruction.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/LLVMContext.h"
#include "llvm/IR/Metadata.h"
#include "llvm/IR/Type.h"
#include "llvm/IR/User.h"
#include "llvm/IR/Value.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Transforms/ObjCARC.h"
#include <cassert>
#include <iterator>
#include <utility>

usingnamespacellvm;
usingnamespacellvm::objcarc;

#define DEBUG_TYPE …

static cl::opt<unsigned> MaxPtrStates("arc-opt-max-ptr-states",
    cl::Hidden,
    cl::desc("Maximum number of ptr states the optimizer keeps track of"),
    cl::init(4095));

/// \defgroup ARCUtilities Utility declarations/definitions specific to ARC.
/// @{

/// This is similar to GetRCIdentityRoot but it stops as soon
/// as it finds a value with multiple uses.
static const Value *FindSingleUseIdentifiedObject(const Value *Arg) { … }

/// @}
///
/// \defgroup ARCOpt ARC Optimization.
/// @{

// TODO: On code like this:
//
// objc_retain(%x)
// stuff_that_cannot_release()
// objc_autorelease(%x)
// stuff_that_cannot_release()
// objc_retain(%x)
// stuff_that_cannot_release()
// objc_autorelease(%x)
//
// The second retain and autorelease can be deleted.

// TODO: It should be possible to delete
// objc_autoreleasePoolPush and objc_autoreleasePoolPop
// pairs if nothing is actually autoreleased between them. Also, autorelease
// calls followed by objc_autoreleasePoolPop calls (perhaps in ObjC++ code
// after inlining) can be turned into plain release calls.

// TODO: Critical-edge splitting. If the optimial insertion point is
// a critical edge, the current algorithm has to fail, because it doesn't
// know how to split edges. It should be possible to make the optimizer
// think in terms of edges, rather than blocks, and then split critical
// edges on demand.

// TODO: OptimizeSequences could generalized to be Interprocedural.

// TODO: Recognize that a bunch of other objc runtime calls have
// non-escaping arguments and non-releasing arguments, and may be
// non-autoreleasing.

// TODO: Sink autorelease calls as far as possible. Unfortunately we
// usually can't sink them past other calls, which would be the main
// case where it would be useful.

// TODO: The pointer returned from objc_loadWeakRetained is retained.

// TODO: Delete release+retain pairs (rare).

STATISTIC(NumNoops,       "Number of no-op objc calls eliminated");
STATISTIC(NumPartialNoops, "Number of partially no-op objc calls eliminated");
STATISTIC(NumAutoreleases,"Number of autoreleases converted to releases");
STATISTIC(NumRets,        "Number of return value forwarding "
                          "retain+autoreleases eliminated");
STATISTIC(NumRRs,         "Number of retain+release paths eliminated");
STATISTIC(NumPeeps,       "Number of calls peephole-optimized");
#ifndef NDEBUG
STATISTIC(NumRetainsBeforeOpt,
          "Number of retains before optimization");
STATISTIC(NumReleasesBeforeOpt,
          "Number of releases before optimization");
STATISTIC(NumRetainsAfterOpt,
          "Number of retains after optimization");
STATISTIC(NumReleasesAfterOpt,
          "Number of releases after optimization");
#endif

namespace {

  /// Per-BasicBlock state.
  class BBState { … };

} // end anonymous namespace

const unsigned BBState::OverflowOccurredValue = …;

namespace llvm {

raw_ostream &operator<<(raw_ostream &OS,
                        BBState &BBState) LLVM_ATTRIBUTE_UNUSED;

} // end namespace llvm

void BBState::InitFromPred(const BBState &Other) { … }

void BBState::InitFromSucc(const BBState &Other) { … }

/// The top-down traversal uses this to merge information about predecessors to
/// form the initial state for a new block.
void BBState::MergePred(const BBState &Other) { … }

/// The bottom-up traversal uses this to merge information about successors to
/// form the initial state for a new block.
void BBState::MergeSucc(const BBState &Other) { … }

raw_ostream &llvm::operator<<(raw_ostream &OS, BBState &BBInfo) { … }

namespace {

  /// The main ARC optimization pass.
class ObjCARCOpt { … };
} // end anonymous namespace

/// Turn objc_retainAutoreleasedReturnValue into objc_retain if the operand is
/// not a return value.
bool
ObjCARCOpt::OptimizeRetainRVCall(Function &F, Instruction *RetainRV) { … }

bool ObjCARCOpt::OptimizeInlinedAutoreleaseRVCall(
    Function &F, Instruction *Inst, const Value *&Arg, ARCInstKind Class,
    Instruction *AutoreleaseRV, const Value *&AutoreleaseRVArg) { … }

/// Turn objc_autoreleaseReturnValue into objc_autorelease if the result is not
/// used as a return value.
void ObjCARCOpt::OptimizeAutoreleaseRVCall(Function &F,
                                           Instruction *AutoreleaseRV,
                                           ARCInstKind &Class) { … }

/// Visit each call, one at a time, and make simplifications without doing any
/// additional analysis.
void ObjCARCOpt::OptimizeIndividualCalls(Function &F) { … }

/// This function returns true if the value is inert. An ObjC ARC runtime call
/// taking an inert operand can be safely deleted.
static bool isInertARCValue(Value *V, SmallPtrSet<Value *, 1> &VisitedPhis) { … }

void ObjCARCOpt::OptimizeIndividualCallImpl(Function &F, Instruction *Inst,
                                            ARCInstKind Class,
                                            const Value *Arg) { … }

/// If we have a top down pointer in the S_Use state, make sure that there are
/// no CFG hazards by checking the states of various bottom up pointers.
static void CheckForUseCFGHazard(const Sequence SuccSSeq,
                                 const bool SuccSRRIKnownSafe,
                                 TopDownPtrState &S,
                                 bool &SomeSuccHasSame,
                                 bool &AllSuccsHaveSame,
                                 bool &NotAllSeqEqualButKnownSafe,
                                 bool &ShouldContinue) { … }

/// If we have a Top Down pointer in the S_CanRelease state, make sure that
/// there are no CFG hazards by checking the states of various bottom up
/// pointers.
static void CheckForCanReleaseCFGHazard(const Sequence SuccSSeq,
                                        const bool SuccSRRIKnownSafe,
                                        TopDownPtrState &S,
                                        bool &SomeSuccHasSame,
                                        bool &AllSuccsHaveSame,
                                        bool &NotAllSeqEqualButKnownSafe) { … }

/// Check for critical edges, loop boundaries, irreducible control flow, or
/// other CFG structures where moving code across the edge would result in it
/// being executed more.
void
ObjCARCOpt::CheckForCFGHazards(const BasicBlock *BB,
                               DenseMap<const BasicBlock *, BBState> &BBStates,
                               BBState &MyStates) const { … }

bool ObjCARCOpt::VisitInstructionBottomUp(
    Instruction *Inst, BasicBlock *BB, BlotMapVector<Value *, RRInfo> &Retains,
    BBState &MyStates) { … }

bool ObjCARCOpt::VisitBottomUp(BasicBlock *BB,
                               DenseMap<const BasicBlock *, BBState> &BBStates,
                               BlotMapVector<Value *, RRInfo> &Retains) { … }

// Fill ReleaseInsertPtToRCIdentityRoots, which is a map from insertion points
// to the set of RC identity roots that would be released by the release calls
// moved to the insertion points.
static void collectReleaseInsertPts(
    const BlotMapVector<Value *, RRInfo> &Retains,
    DenseMap<const Instruction *, SmallPtrSet<const Value *, 2>>
        &ReleaseInsertPtToRCIdentityRoots) { … }

// Get the RC identity roots from an insertion point of an objc_release call.
// Return nullptr if the passed instruction isn't an insertion point.
static const SmallPtrSet<const Value *, 2> *
getRCIdentityRootsFromReleaseInsertPt(
    const Instruction *InsertPt,
    const DenseMap<const Instruction *, SmallPtrSet<const Value *, 2>>
        &ReleaseInsertPtToRCIdentityRoots) { … }

bool ObjCARCOpt::VisitInstructionTopDown(
    Instruction *Inst, DenseMap<Value *, RRInfo> &Releases, BBState &MyStates,
    const DenseMap<const Instruction *, SmallPtrSet<const Value *, 2>>
        &ReleaseInsertPtToRCIdentityRoots) { … }

bool ObjCARCOpt::VisitTopDown(
    BasicBlock *BB, DenseMap<const BasicBlock *, BBState> &BBStates,
    DenseMap<Value *, RRInfo> &Releases,
    const DenseMap<const Instruction *, SmallPtrSet<const Value *, 2>>
        &ReleaseInsertPtToRCIdentityRoots) { … }

static void
ComputePostOrders(Function &F,
                  SmallVectorImpl<BasicBlock *> &PostOrder,
                  SmallVectorImpl<BasicBlock *> &ReverseCFGPostOrder,
                  unsigned NoObjCARCExceptionsMDKind,
                  DenseMap<const BasicBlock *, BBState> &BBStates) { … }

// Visit the function both top-down and bottom-up.
bool ObjCARCOpt::Visit(Function &F,
                       DenseMap<const BasicBlock *, BBState> &BBStates,
                       BlotMapVector<Value *, RRInfo> &Retains,
                       DenseMap<Value *, RRInfo> &Releases) { … }

/// Move the calls in RetainsToMove and ReleasesToMove.
void ObjCARCOpt::MoveCalls(Value *Arg, RRInfo &RetainsToMove,
                           RRInfo &ReleasesToMove,
                           BlotMapVector<Value *, RRInfo> &Retains,
                           DenseMap<Value *, RRInfo> &Releases,
                           SmallVectorImpl<Instruction *> &DeadInsts,
                           Module *M) { … }

bool ObjCARCOpt::PairUpRetainsAndReleases(
    DenseMap<const BasicBlock *, BBState> &BBStates,
    BlotMapVector<Value *, RRInfo> &Retains,
    DenseMap<Value *, RRInfo> &Releases, Module *M,
    Instruction *Retain,
    SmallVectorImpl<Instruction *> &DeadInsts, RRInfo &RetainsToMove,
    RRInfo &ReleasesToMove, Value *Arg, bool KnownSafe,
    bool &AnyPairsCompletelyEliminated) { … }

/// Identify pairings between the retains and releases, and delete and/or move
/// them.
bool ObjCARCOpt::PerformCodePlacement(
    DenseMap<const BasicBlock *, BBState> &BBStates,
    BlotMapVector<Value *, RRInfo> &Retains,
    DenseMap<Value *, RRInfo> &Releases, Module *M) { … }

/// Weak pointer optimizations.
void ObjCARCOpt::OptimizeWeakCalls(Function &F) { … }

/// Identify program paths which execute sequences of retains and releases which
/// can be eliminated.
bool ObjCARCOpt::OptimizeSequences(Function &F) { … }

/// Check if there is a dependent call earlier that does not have anything in
/// between the Retain and the call that can affect the reference count of their
/// shared pointer argument. Note that Retain need not be in BB.
static CallInst *HasSafePathToPredecessorCall(const Value *Arg,
                                              Instruction *Retain,
                                              ProvenanceAnalysis &PA) { … }

/// Find a dependent retain that precedes the given autorelease for which there
/// is nothing in between the two instructions that can affect the ref count of
/// Arg.
static CallInst *
FindPredecessorRetainWithSafePath(const Value *Arg, BasicBlock *BB,
                                  Instruction *Autorelease,
                                  ProvenanceAnalysis &PA) { … }

/// Look for an ``autorelease'' instruction dependent on Arg such that there are
/// no instructions dependent on Arg that need a positive ref count in between
/// the autorelease and the ret.
static CallInst *
FindPredecessorAutoreleaseWithSafePath(const Value *Arg, BasicBlock *BB,
                                       ReturnInst *Ret,
                                       ProvenanceAnalysis &PA) { … }

/// Look for this pattern:
/// \code
///    %call = call i8* @something(...)
///    %2 = call i8* @objc_retain(i8* %call)
///    %3 = call i8* @objc_autorelease(i8* %2)
///    ret i8* %3
/// \endcode
/// And delete the retain and autorelease.
void ObjCARCOpt::OptimizeReturns(Function &F) { … }

#ifndef NDEBUG
void
ObjCARCOpt::GatherStatistics(Function &F, bool AfterOptimization) {
  Statistic &NumRetains =
      AfterOptimization ? NumRetainsAfterOpt : NumRetainsBeforeOpt;
  Statistic &NumReleases =
      AfterOptimization ? NumReleasesAfterOpt : NumReleasesBeforeOpt;

  for (inst_iterator I = inst_begin(&F), E = inst_end(&F); I != E; ) {
    Instruction *Inst = &*I++;
    switch (GetBasicARCInstKind(Inst)) {
    default:
      break;
    case ARCInstKind::Retain:
      ++NumRetains;
      break;
    case ARCInstKind::Release:
      ++NumReleases;
      break;
    }
  }
}
#endif

void ObjCARCOpt::init(Function &F) { … }

bool ObjCARCOpt::run(Function &F, AAResults &AA) { … }

/// @}
///

PreservedAnalyses ObjCARCOptPass::run(Function &F,
                                      FunctionAnalysisManager &AM) { … }