1//===- ProvenanceAnalysis.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//
9/// \file
10///
11/// This file defines a special form of Alias Analysis called ``Provenance
12/// Analysis''. The word ``provenance'' refers to the history of the ownership
13/// of an object. Thus ``Provenance Analysis'' is an analysis which attempts to
14/// use various techniques to determine if locally
15///
16/// WARNING: This file knows about certain library functions. It recognizes them
17/// by name, and hardwires knowledge of their semantics.
18///
19/// WARNING: This file knows about how certain Objective-C library functions are
20/// used. Naive LLVM IR transformations which would otherwise be
21/// behavior-preserving may break these assumptions.
22//
23//===----------------------------------------------------------------------===//
24
25#include "ProvenanceAnalysis.h"
26#include "llvm/ADT/SmallPtrSet.h"
27#include "llvm/ADT/SmallVector.h"
28#include "llvm/Analysis/AliasAnalysis.h"
29#include "llvm/Analysis/ObjCARCAnalysisUtils.h"
30#include "llvm/IR/Instructions.h"
31#include "llvm/IR/Module.h"
32#include "llvm/IR/Use.h"
33#include "llvm/IR/User.h"
34#include "llvm/IR/Value.h"
35#include "llvm/Support/Casting.h"
36#include <utility>
37
38using namespace llvm;
39using namespace llvm::objcarc;
40
41bool ProvenanceAnalysis::relatedSelect(const SelectInst *A,
42                                       const Value *B) {
43  // If the values are Selects with the same condition, we can do a more precise
44  // check: just check for relations between the values on corresponding arms.
45  if (const SelectInst *SB = dyn_cast<SelectInst>(B))
46    if (A->getCondition() == SB->getCondition())
47      return related(A->getTrueValue(), SB->getTrueValue()) ||
48             related(A->getFalseValue(), SB->getFalseValue());
49
50  // Check both arms of the Select node individually.
51  return related(A->getTrueValue(), B) || related(A->getFalseValue(), B);
52}
53
54bool ProvenanceAnalysis::relatedPHI(const PHINode *A,
55                                    const Value *B) {
56  // If the values are PHIs in the same block, we can do a more precise as well
57  // as efficient check: just check for relations between the values on
58  // corresponding edges.
59  if (const PHINode *PNB = dyn_cast<PHINode>(B))
60    if (PNB->getParent() == A->getParent()) {
61      for (unsigned i = 0, e = A->getNumIncomingValues(); i != e; ++i)
62        if (related(A->getIncomingValue(i),
63                    PNB->getIncomingValueForBlock(A->getIncomingBlock(i))))
64          return true;
65      return false;
66    }
67
68  // Check each unique source of the PHI node against B.
69  SmallPtrSet<const Value *, 4> UniqueSrc;
70  for (Value *PV1 : A->incoming_values()) {
71    if (UniqueSrc.insert(PV1).second && related(PV1, B))
72      return true;
73  }
74
75  // All of the arms checked out.
76  return false;
77}
78
79/// Test if the value of P, or any value covered by its provenance, is ever
80/// stored within the function (not counting callees).
81static bool IsStoredObjCPointer(const Value *P) {
82  SmallPtrSet<const Value *, 8> Visited;
83  SmallVector<const Value *, 8> Worklist;
84  Worklist.push_back(P);
85  Visited.insert(P);
86  do {
87    P = Worklist.pop_back_val();
88    for (const Use &U : P->uses()) {
89      const User *Ur = U.getUser();
90      if (isa<StoreInst>(Ur)) {
91        if (U.getOperandNo() == 0)
92          // The pointer is stored.
93          return true;
94        // The pointed is stored through.
95        continue;
96      }
97      if (isa<CallInst>(Ur))
98        // The pointer is passed as an argument, ignore this.
99        continue;
100      if (isa<PtrToIntInst>(P))
101        // Assume the worst.
102        return true;
103      if (Visited.insert(Ur).second)
104        Worklist.push_back(Ur);
105    }
106  } while (!Worklist.empty());
107
108  // Everything checked out.
109  return false;
110}
111
112bool ProvenanceAnalysis::relatedCheck(const Value *A, const Value *B) {
113  // Ask regular AliasAnalysis, for a first approximation.
114  switch (AA->alias(A, B)) {
115  case AliasResult::NoAlias:
116    return false;
117  case AliasResult::MustAlias:
118  case AliasResult::PartialAlias:
119    return true;
120  case AliasResult::MayAlias:
121    break;
122  }
123
124  bool AIsIdentified = IsObjCIdentifiedObject(A);
125  bool BIsIdentified = IsObjCIdentifiedObject(B);
126
127  // An ObjC-Identified object can't alias a load if it is never locally stored.
128  if (AIsIdentified) {
129    // Check for an obvious escape.
130    if (isa<LoadInst>(B))
131      return IsStoredObjCPointer(A);
132    if (BIsIdentified) {
133      // Check for an obvious escape.
134      if (isa<LoadInst>(A))
135        return IsStoredObjCPointer(B);
136      // Both pointers are identified and escapes aren't an evident problem.
137      return false;
138    }
139  } else if (BIsIdentified) {
140    // Check for an obvious escape.
141    if (isa<LoadInst>(A))
142      return IsStoredObjCPointer(B);
143  }
144
145   // Special handling for PHI and Select.
146  if (const PHINode *PN = dyn_cast<PHINode>(A))
147    return relatedPHI(PN, B);
148  if (const PHINode *PN = dyn_cast<PHINode>(B))
149    return relatedPHI(PN, A);
150  if (const SelectInst *S = dyn_cast<SelectInst>(A))
151    return relatedSelect(S, B);
152  if (const SelectInst *S = dyn_cast<SelectInst>(B))
153    return relatedSelect(S, A);
154
155  // Conservative.
156  return true;
157}
158
159bool ProvenanceAnalysis::related(const Value *A, const Value *B) {
160  A = GetUnderlyingObjCPtrCached(A, UnderlyingObjCPtrCache);
161  B = GetUnderlyingObjCPtrCached(B, UnderlyingObjCPtrCache);
162
163  // Quick check.
164  if (A == B)
165    return true;
166
167  // Begin by inserting a conservative value into the map. If the insertion
168  // fails, we have the answer already. If it succeeds, leave it there until we
169  // compute the real answer to guard against recursive queries.
170  std::pair<CachedResultsTy::iterator, bool> Pair =
171    CachedResults.insert(std::make_pair(ValuePairTy(A, B), true));
172  if (!Pair.second)
173    return Pair.first->second;
174
175  bool Result = relatedCheck(A, B);
176  CachedResults[ValuePairTy(A, B)] = Result;
177  return Result;
178}
179