LLVM  17.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 B individually. Return false if neither arm is related
51  // to A.
52  if (!(related(SB->getTrueValue(), A) || related(SB->getFalseValue(), A)))
53  return false;
54  }
55 
56  // Check both arms of the Select node individually.
57  return related(A->getTrueValue(), B) || related(A->getFalseValue(), B);
58 }
59 
60 bool ProvenanceAnalysis::relatedPHI(const PHINode *A,
61  const Value *B) {
62 
63  auto comparePHISources = [this](const PHINode *PNA, const Value *B) -> bool {
64  // Check each unique source of the PHI node against B.
66  for (Value *PV1 : PNA->incoming_values()) {
67  if (UniqueSrc.insert(PV1).second && related(PV1, B))
68  return true;
69  }
70 
71  // All of the arms checked out.
72  return false;
73  };
74 
75  if (const PHINode *PNB = dyn_cast<PHINode>(B)) {
76  // If the values are PHIs in the same block, we can do a more precise as
77  // well as efficient check: just check for relations between the values on
78  // corresponding edges.
79  if (PNB->getParent() == A->getParent()) {
80  for (unsigned i = 0, e = A->getNumIncomingValues(); i != e; ++i)
81  if (related(A->getIncomingValue(i),
82  PNB->getIncomingValueForBlock(A->getIncomingBlock(i))))
83  return true;
84  return false;
85  }
86 
87  if (!comparePHISources(PNB, A))
88  return false;
89  }
90 
91  return comparePHISources(A, B);
92 }
93 
94 /// Test if the value of P, or any value covered by its provenance, is ever
95 /// stored within the function (not counting callees).
96 static bool IsStoredObjCPointer(const Value *P) {
99  Worklist.push_back(P);
100  Visited.insert(P);
101  do {
102  P = Worklist.pop_back_val();
103  for (const Use &U : P->uses()) {
104  const User *Ur = U.getUser();
105  if (isa<StoreInst>(Ur)) {
106  if (U.getOperandNo() == 0)
107  // The pointer is stored.
108  return true;
109  // The pointed is stored through.
110  continue;
111  }
112  if (isa<CallInst>(Ur))
113  // The pointer is passed as an argument, ignore this.
114  continue;
115  if (isa<PtrToIntInst>(P))
116  // Assume the worst.
117  return true;
118  if (Visited.insert(Ur).second)
119  Worklist.push_back(Ur);
120  }
121  } while (!Worklist.empty());
122 
123  // Everything checked out.
124  return false;
125 }
126 
127 bool ProvenanceAnalysis::relatedCheck(const Value *A, const Value *B) {
128  // Ask regular AliasAnalysis, for a first approximation.
129  switch (AA->alias(A, B)) {
131  return false;
134  return true;
136  break;
137  }
138 
139  bool AIsIdentified = IsObjCIdentifiedObject(A);
140  bool BIsIdentified = IsObjCIdentifiedObject(B);
141 
142  // An ObjC-Identified object can't alias a load if it is never locally stored.
143 
144  // Check for an obvious escape.
145  if ((AIsIdentified && isa<LoadInst>(B) && !IsStoredObjCPointer(A)) ||
146  (BIsIdentified && isa<LoadInst>(A) && !IsStoredObjCPointer(B)))
147  return false;
148 
149  if ((AIsIdentified && isa<LoadInst>(B)) ||
150  (BIsIdentified && isa<LoadInst>(A)))
151  return true;
152 
153  // Both pointers are identified and escapes aren't an evident problem.
154  if (AIsIdentified && BIsIdentified && !isa<LoadInst>(A) && !isa<LoadInst>(B))
155  return false;
156 
157  // Special handling for PHI and Select.
158  if (const PHINode *PN = dyn_cast<PHINode>(A))
159  return relatedPHI(PN, B);
160  if (const PHINode *PN = dyn_cast<PHINode>(B))
161  return relatedPHI(PN, A);
162  if (const SelectInst *S = dyn_cast<SelectInst>(A))
163  return relatedSelect(S, B);
164  if (const SelectInst *S = dyn_cast<SelectInst>(B))
165  return relatedSelect(S, A);
166 
167  // Conservative.
168  return true;
169 }
170 
171 bool ProvenanceAnalysis::related(const Value *A, const Value *B) {
172  A = GetUnderlyingObjCPtrCached(A, UnderlyingObjCPtrCache);
173  B = GetUnderlyingObjCPtrCached(B, UnderlyingObjCPtrCache);
174 
175  // Quick check.
176  if (A == B)
177  return true;
178 
179  // Begin by inserting a conservative value into the map. If the insertion
180  // fails, we have the answer already. If it succeeds, leave it there until we
181  // compute the real answer to guard against recursive queries.
182  if (A > B) std::swap(A, B);
183  std::pair<CachedResultsTy::iterator, bool> Pair =
184  CachedResults.insert(std::make_pair(ValuePairTy(A, B), true));
185  if (!Pair.second)
186  return Pair.first->second;
187 
188  bool Result = relatedCheck(A, B);
189  assert(relatedCheck(B, A) == Result &&
190  "relatedCheck result depending on order of parameters!");
191  CachedResults[ValuePairTy(A, B)] = Result;
192  return Result;
193 }
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:2784
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:81
ProvenanceAnalysis.h
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:31
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:1746
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:186
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:105
Instructions.h
SmallVector.h
User.h
llvm::SmallVectorImpl::pop_back_val
T pop_back_val()
Definition: SmallVector.h:677
llvm::PHINode
Definition: Instructions.h:2708
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:96
llvm::objcarc::ProvenanceAnalysis::related
bool related(const Value *A, const Value *B)
Definition: ProvenanceAnalysis.cpp:171
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