LLVM  16.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"
26 #include "llvm/ADT/SmallPtrSet.h"
27 #include "llvm/ADT/SmallVector.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 
38 using namespace llvm;
39 using namespace llvm::objcarc;
40 
41 bool 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 
54 bool ProvenanceAnalysis::relatedPHI(const PHINode *A,
55  const Value *B) {
56 
57  auto comparePHISources = [this](const PHINode *PNA, const Value *B) -> bool {
58  // Check each unique source of the PHI node against B.
60  for (Value *PV1 : PNA->incoming_values()) {
61  if (UniqueSrc.insert(PV1).second && related(PV1, B))
62  return true;
63  }
64 
65  // All of the arms checked out.
66  return false;
67  };
68 
69  if (const PHINode *PNB = dyn_cast<PHINode>(B)) {
70  // If the values are PHIs in the same block, we can do a more precise as
71  // well as efficient check: just check for relations between the values on
72  // corresponding edges.
73  if (PNB->getParent() == A->getParent()) {
74  for (unsigned i = 0, e = A->getNumIncomingValues(); i != e; ++i)
75  if (related(A->getIncomingValue(i),
76  PNB->getIncomingValueForBlock(A->getIncomingBlock(i))))
77  return true;
78  return false;
79  }
80 
81  if (!comparePHISources(PNB, A))
82  return false;
83  }
84 
85  return comparePHISources(A, B);
86 }
87 
88 /// Test if the value of P, or any value covered by its provenance, is ever
89 /// stored within the function (not counting callees).
90 static bool IsStoredObjCPointer(const Value *P) {
93  Worklist.push_back(P);
94  Visited.insert(P);
95  do {
96  P = Worklist.pop_back_val();
97  for (const Use &U : P->uses()) {
98  const User *Ur = U.getUser();
99  if (isa<StoreInst>(Ur)) {
100  if (U.getOperandNo() == 0)
101  // The pointer is stored.
102  return true;
103  // The pointed is stored through.
104  continue;
105  }
106  if (isa<CallInst>(Ur))
107  // The pointer is passed as an argument, ignore this.
108  continue;
109  if (isa<PtrToIntInst>(P))
110  // Assume the worst.
111  return true;
112  if (Visited.insert(Ur).second)
113  Worklist.push_back(Ur);
114  }
115  } while (!Worklist.empty());
116 
117  // Everything checked out.
118  return false;
119 }
120 
121 bool ProvenanceAnalysis::relatedCheck(const Value *A, const Value *B) {
122  // Ask regular AliasAnalysis, for a first approximation.
123  switch (AA->alias(A, B)) {
125  return false;
128  return true;
130  break;
131  }
132 
133  bool AIsIdentified = IsObjCIdentifiedObject(A);
134  bool BIsIdentified = IsObjCIdentifiedObject(B);
135 
136  // An ObjC-Identified object can't alias a load if it is never locally stored.
137 
138  // Check for an obvious escape.
139  if ((AIsIdentified && isa<LoadInst>(B) && !IsStoredObjCPointer(A)) ||
140  (BIsIdentified && isa<LoadInst>(A) && !IsStoredObjCPointer(B)))
141  return false;
142 
143  if ((AIsIdentified && isa<LoadInst>(B)) ||
144  (BIsIdentified && isa<LoadInst>(A)))
145  return true;
146 
147  // Both pointers are identified and escapes aren't an evident problem.
148  if (AIsIdentified && BIsIdentified && !isa<LoadInst>(A) && !isa<LoadInst>(B))
149  return false;
150 
151  // Special handling for PHI and Select.
152  if (const PHINode *PN = dyn_cast<PHINode>(A))
153  return relatedPHI(PN, B);
154  if (const PHINode *PN = dyn_cast<PHINode>(B))
155  return relatedPHI(PN, A);
156  if (const SelectInst *S = dyn_cast<SelectInst>(A))
157  return relatedSelect(S, B);
158  if (const SelectInst *S = dyn_cast<SelectInst>(B))
159  return relatedSelect(S, A);
160 
161  // Conservative.
162  return true;
163 }
164 
165 bool ProvenanceAnalysis::related(const Value *A, const Value *B) {
166  A = GetUnderlyingObjCPtrCached(A, UnderlyingObjCPtrCache);
167  B = GetUnderlyingObjCPtrCached(B, UnderlyingObjCPtrCache);
168 
169  // Quick check.
170  if (A == B)
171  return true;
172 
173  // Begin by inserting a conservative value into the map. If the insertion
174  // fails, we have the answer already. If it succeeds, leave it there until we
175  // compute the real answer to guard against recursive queries.
176  if (A > B) std::swap(A, B);
177  std::pair<CachedResultsTy::iterator, bool> Pair =
178  CachedResults.insert(std::make_pair(ValuePairTy(A, B), true));
179  if (!Pair.second)
180  return Pair.first->second;
181 
182  bool Result = relatedCheck(A, B);
183  assert(relatedCheck(B, A) == Result &&
184  "relatedCheck result depending on order of parameters!");
185  CachedResults[ValuePairTy(A, B)] = Result;
186  return Result;
187 }
i
i
Definition: README.txt:29
llvm::AliasResult::MayAlias
@ MayAlias
The two locations may or may not alias.
Definition: AliasAnalysis.h:104
llvm::AliasResult::PartialAlias
@ PartialAlias
The two locations alias, but only due to a partial overlap.
Definition: AliasAnalysis.h:106
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
llvm::PHINode::incoming_values
op_range incoming_values()
Definition: Instructions.h:2785
P
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper which DAGCombine can t really do The code for turning x load into a single vector load is target independent and should be moved to the dag combiner The code for turning x load into a vector load can only handle a direct load from a global or a direct load from the stack It should be generalized to handle any load from P
Definition: README-SSE.txt:411
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1199
Module.h
llvm::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:450
Use.h
AliasAnalysis.h
llvm::User
Definition: User.h:44
llvm::ARM_PROC::A
@ A
Definition: ARMBaseInfo.h:34
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
SmallPtrSet.h
llvm::objcarc::GetUnderlyingObjCPtrCached
const Value * GetUnderlyingObjCPtrCached(const Value *V, DenseMap< const Value *, std::pair< WeakVH, WeakTrackingVH >> &Cache)
A wrapper for GetUnderlyingObjCPtr used for results memoization.
Definition: ObjCARCAnalysisUtils.h:82
ProvenanceAnalysis.h
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:53
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
std::swap
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:853
llvm::SelectInst
This class represents the LLVM 'select' instruction.
Definition: Instructions.h:1737
llvm::objcarc
Definition: ObjCARCAliasAnalysis.h:29
llvm::objcarc::IsObjCIdentifiedObject
bool IsObjCIdentifiedObject(const Value *V)
Return true if this value refers to a distinct and identifiable object.
Definition: ObjCARCAnalysisUtils.h:187
llvm::AliasResult::NoAlias
@ NoAlias
The two locations do not alias at all.
Definition: AliasAnalysis.h:101
llvm::AliasResult::MustAlias
@ MustAlias
The two locations precisely alias each other.
Definition: AliasAnalysis.h:108
S
add sub stmia L5 ldr r0 bl L_printf $stub Instead of a and a wouldn t it be better to do three moves *Return an aggregate type is even return S
Definition: README.txt:210
llvm::DenseMapBase::insert
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:207
ObjCARCAnalysisUtils.h
Casting.h
llvm::AAResults::alias
AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB)
The main low level interface to the alias analysis implementation.
Definition: AliasAnalysis.cpp:107
Instructions.h
SmallVector.h
User.h
llvm::SmallVectorImpl::pop_back_val
T pop_back_val()
Definition: SmallVector.h:677
llvm::PHINode
Definition: Instructions.h:2699
IsStoredObjCPointer
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...
Definition: ProvenanceAnalysis.cpp:90
llvm::objcarc::ProvenanceAnalysis::related
bool related(const Value *A, const Value *B)
Definition: ProvenanceAnalysis.cpp:165
Value.h
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
llvm::SmallPtrSetImpl::insert
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:365