LLVM  14.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  // 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).
81 static 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 
112 bool 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 
159 bool 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  if (A > B) std::swap(A, B);
171  std::pair<CachedResultsTy::iterator, bool> Pair =
172  CachedResults.insert(std::make_pair(ValuePairTy(A, B), true));
173  if (!Pair.second)
174  return Pair.first->second;
175 
176  bool Result = relatedCheck(A, B);
177  CachedResults[ValuePairTy(A, B)] = Result;
178  return Result;
179 }
i
i
Definition: README.txt:29
llvm::AliasResult::MayAlias
@ MayAlias
The two locations may or may not alias.
Definition: AliasAnalysis.h:102
llvm::AliasResult::PartialAlias
@ PartialAlias
The two locations alias, but only due to a partial overlap.
Definition: AliasAnalysis.h:104
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
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:1168
Module.h
llvm::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:449
llvm::SmallVectorImpl::pop_back_val
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:635
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
ProvenanceAnalysis.h
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:57
llvm::objcarc::GetUnderlyingObjCPtrCached
const Value * GetUnderlyingObjCPtrCached(const Value *V, DenseMap< const Value *, WeakTrackingVH > &Cache)
A wrapper for GetUnderlyingObjCPtr used for results memoization.
Definition: ObjCARCAnalysisUtils.h:82
std::swap
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:840
llvm::SelectInst
This class represents the LLVM 'select' instruction.
Definition: Instructions.h:1738
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:183
llvm::AliasResult::NoAlias
@ NoAlias
The two locations do not alias at all.
Definition: AliasAnalysis.h:99
llvm::AliasResult::MustAlias
@ MustAlias
The two locations precisely alias each other.
Definition: AliasAnalysis.h:106
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:120
Instructions.h
SmallVector.h
User.h
llvm::PHINode
Definition: Instructions.h:2625
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:81
llvm::objcarc::ProvenanceAnalysis::related
bool related(const Value *A, const Value *B)
Definition: ProvenanceAnalysis.cpp:159
Value.h
llvm::Value
LLVM Value Representation.
Definition: Value.h:75
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:44
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:364