1 //===- ProvenanceAnalysis.cpp - ObjC ARC Optimization ---------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
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
16 /// WARNING: This file knows about certain library functions. It recognizes them
17 /// by name, and hardwires knowledge of their semantics.
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.
23 //===----------------------------------------------------------------------===//
26 #include "ProvenanceAnalysis.h"
27 #include "llvm/ADT/STLExtras.h"
28 #include "llvm/ADT/SmallPtrSet.h"
31 using namespace llvm::objcarc;
33 bool ProvenanceAnalysis::relatedSelect(const SelectInst *A,
35 // If the values are Selects with the same condition, we can do a more precise
36 // check: just check for relations between the values on corresponding arms.
37 if (const SelectInst *SB = dyn_cast<SelectInst>(B))
38 if (A->getCondition() == SB->getCondition())
39 return related(A->getTrueValue(), SB->getTrueValue()) ||
40 related(A->getFalseValue(), SB->getFalseValue());
42 // Check both arms of the Select node individually.
43 return related(A->getTrueValue(), B) ||
44 related(A->getFalseValue(), B);
47 bool ProvenanceAnalysis::relatedPHI(const PHINode *A,
49 // If the values are PHIs in the same block, we can do a more precise as well
50 // as efficient check: just check for relations between the values on
51 // corresponding edges.
52 if (const PHINode *PNB = dyn_cast<PHINode>(B))
53 if (PNB->getParent() == A->getParent()) {
54 for (unsigned i = 0, e = A->getNumIncomingValues(); i != e; ++i)
55 if (related(A->getIncomingValue(i),
56 PNB->getIncomingValueForBlock(A->getIncomingBlock(i))))
61 // Check each unique source of the PHI node against B.
62 SmallPtrSet<const Value *, 4> UniqueSrc;
63 for (unsigned i = 0, e = A->getNumIncomingValues(); i != e; ++i) {
64 const Value *PV1 = A->getIncomingValue(i);
65 if (UniqueSrc.insert(PV1) && related(PV1, B))
69 // All of the arms checked out.
73 /// Test if the value of P, or any value covered by its provenance, is ever
74 /// stored within the function (not counting callees).
75 static bool IsStoredObjCPointer(const Value *P) {
76 SmallPtrSet<const Value *, 8> Visited;
77 SmallVector<const Value *, 8> Worklist;
78 Worklist.push_back(P);
81 P = Worklist.pop_back_val();
82 for (Value::const_use_iterator UI = P->use_begin(), UE = P->use_end();
85 if (isa<StoreInst>(Ur)) {
86 if (UI.getOperandNo() == 0)
87 // The pointer is stored.
89 // The pointed is stored through.
92 if (isa<CallInst>(Ur))
93 // The pointer is passed as an argument, ignore this.
95 if (isa<PtrToIntInst>(P))
98 if (Visited.insert(Ur))
99 Worklist.push_back(Ur);
101 } while (!Worklist.empty());
103 // Everything checked out.
107 bool ProvenanceAnalysis::relatedCheck(const Value *A,
109 // Skip past provenance pass-throughs.
110 A = GetUnderlyingObjCPtr(A);
111 B = GetUnderlyingObjCPtr(B);
117 // Ask regular AliasAnalysis, for a first approximation.
118 switch (AA->alias(A, B)) {
119 case AliasAnalysis::NoAlias:
121 case AliasAnalysis::MustAlias:
122 case AliasAnalysis::PartialAlias:
124 case AliasAnalysis::MayAlias:
128 bool AIsIdentified = IsObjCIdentifiedObject(A);
129 bool BIsIdentified = IsObjCIdentifiedObject(B);
131 // An ObjC-Identified object can't alias a load if it is never locally stored.
133 // Check for an obvious escape.
134 if (isa<LoadInst>(B))
135 return IsStoredObjCPointer(A);
137 // Check for an obvious escape.
138 if (isa<LoadInst>(A))
139 return IsStoredObjCPointer(B);
140 // Both pointers are identified and escapes aren't an evident problem.
143 } else if (BIsIdentified) {
144 // Check for an obvious escape.
145 if (isa<LoadInst>(A))
146 return IsStoredObjCPointer(B);
149 // Special handling for PHI and Select.
150 if (const PHINode *PN = dyn_cast<PHINode>(A))
151 return relatedPHI(PN, B);
152 if (const PHINode *PN = dyn_cast<PHINode>(B))
153 return relatedPHI(PN, A);
154 if (const SelectInst *S = dyn_cast<SelectInst>(A))
155 return relatedSelect(S, B);
156 if (const SelectInst *S = dyn_cast<SelectInst>(B))
157 return relatedSelect(S, A);
163 bool ProvenanceAnalysis::related(const Value *A,
165 // Begin by inserting a conservative value into the map. If the insertion
166 // fails, we have the answer already. If it succeeds, leave it there until we
167 // compute the real answer to guard against recursive queries.
168 if (A > B) std::swap(A, B);
169 std::pair<CachedResultsTy::iterator, bool> Pair =
170 CachedResults.insert(std::make_pair(ValuePairTy(A, B), true));
172 return Pair.first->second;
174 bool Result = relatedCheck(A, B);
175 CachedResults[ValuePairTy(A, B)] = Result;