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