LLVM 20.0.0git
ProvenanceAnalysis.cpp
Go to the documentation of this file.
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"
31#include "llvm/IR/Module.h"
32#include "llvm/IR/Use.h"
33#include "llvm/IR/User.h"
34#include "llvm/IR/Value.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.
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) {
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)) {
116 return false;
119 return true;
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
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}
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
This defines the Use class.
Module.h This file contains the declarations for the Module class.
This file defines common analysis utilities used by the ObjC ARC Optimizer.
#define P(N)
static bool IsStoredObjCPointer(const Value *P)
Test if the value of P, or any value covered by its provenance, is ever stored within the function (n...
This file declares a special form of Alias Analysis called Provenance Analysis''.
This file defines the SmallPtrSet class.
This file defines the SmallVector class.
AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB)
The main low level interface to the alias analysis implementation.
@ MayAlias
The two locations may or may not alias.
@ NoAlias
The two locations do not alias at all.
@ PartialAlias
The two locations alias, but only due to a partial overlap.
@ MustAlias
The two locations precisely alias each other.
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:211
This class represents the LLVM 'select' instruction.
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:368
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:503
bool empty() const
Definition: SmallVector.h:95
void push_back(const T &Elt)
Definition: SmallVector.h:427
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1210
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
LLVM Value Representation.
Definition: Value.h:74
bool related(const Value *A, const Value *B)
bool IsObjCIdentifiedObject(const Value *V)
Return true if this value refers to a distinct and identifiable object.
const Value * GetUnderlyingObjCPtrCached(const Value *V, DenseMap< const Value *, std::pair< WeakVH, WeakTrackingVH > > &Cache)
A wrapper for GetUnderlyingObjCPtr used for results memoization.
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18