blob: 9ffdfb4f7f9c6a1c24f94f0f451464c0dcf3c0a0 [file] [log] [blame]
Michael Gottesman778138e2013-01-29 03:03:03 +00001//===- ProvenanceAnalysis.cpp - ObjC ARC Optimization ---------------------===//
2//
3// The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
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 "ObjCARC.h"
26#include "ProvenanceAnalysis.h"
Michael Gottesman778138e2013-01-29 03:03:03 +000027#include "llvm/ADT/STLExtras.h"
Michael Gottesman278266f2013-01-29 04:20:52 +000028#include "llvm/ADT/SmallPtrSet.h"
Michael Gottesman778138e2013-01-29 03:03:03 +000029
30using namespace llvm;
31using namespace llvm::objcarc;
32
33bool ProvenanceAnalysis::relatedSelect(const SelectInst *A,
34 const Value *B) {
Mehdi Aminia28d91d2015-03-10 02:37:25 +000035 const DataLayout &DL = A->getModule()->getDataLayout();
Michael Gottesman778138e2013-01-29 03:03:03 +000036 // If the values are Selects with the same condition, we can do a more precise
37 // check: just check for relations between the values on corresponding arms.
38 if (const SelectInst *SB = dyn_cast<SelectInst>(B))
39 if (A->getCondition() == SB->getCondition())
Mehdi Aminia28d91d2015-03-10 02:37:25 +000040 return related(A->getTrueValue(), SB->getTrueValue(), DL) ||
41 related(A->getFalseValue(), SB->getFalseValue(), DL);
Michael Gottesman778138e2013-01-29 03:03:03 +000042
43 // Check both arms of the Select node individually.
Mehdi Aminia28d91d2015-03-10 02:37:25 +000044 return related(A->getTrueValue(), B, DL) ||
45 related(A->getFalseValue(), B, DL);
Michael Gottesman778138e2013-01-29 03:03:03 +000046}
47
48bool ProvenanceAnalysis::relatedPHI(const PHINode *A,
49 const Value *B) {
Mehdi Aminia28d91d2015-03-10 02:37:25 +000050 const DataLayout &DL = A->getModule()->getDataLayout();
Michael Gottesman778138e2013-01-29 03:03:03 +000051 // If the values are PHIs in the same block, we can do a more precise as well
52 // as efficient check: just check for relations between the values on
53 // corresponding edges.
54 if (const PHINode *PNB = dyn_cast<PHINode>(B))
55 if (PNB->getParent() == A->getParent()) {
56 for (unsigned i = 0, e = A->getNumIncomingValues(); i != e; ++i)
57 if (related(A->getIncomingValue(i),
Mehdi Aminia28d91d2015-03-10 02:37:25 +000058 PNB->getIncomingValueForBlock(A->getIncomingBlock(i)), DL))
Michael Gottesman778138e2013-01-29 03:03:03 +000059 return true;
60 return false;
61 }
62
63 // Check each unique source of the PHI node against B.
64 SmallPtrSet<const Value *, 4> UniqueSrc;
Pete Cooper833f34d2015-05-12 20:05:31 +000065 for (Value *PV1 : A->incoming_values()) {
Mehdi Aminia28d91d2015-03-10 02:37:25 +000066 if (UniqueSrc.insert(PV1).second && related(PV1, B, DL))
Michael Gottesman778138e2013-01-29 03:03:03 +000067 return true;
68 }
69
70 // All of the arms checked out.
71 return false;
72}
73
74/// Test if the value of P, or any value covered by its provenance, is ever
75/// stored within the function (not counting callees).
Michael Gottesman27029f42013-02-12 23:35:08 +000076static bool IsStoredObjCPointer(const Value *P) {
Michael Gottesman778138e2013-01-29 03:03:03 +000077 SmallPtrSet<const Value *, 8> Visited;
78 SmallVector<const Value *, 8> Worklist;
79 Worklist.push_back(P);
80 Visited.insert(P);
81 do {
82 P = Worklist.pop_back_val();
Chandler Carruthcdf47882014-03-09 03:16:01 +000083 for (const Use &U : P->uses()) {
84 const User *Ur = U.getUser();
Michael Gottesman778138e2013-01-29 03:03:03 +000085 if (isa<StoreInst>(Ur)) {
Chandler Carruthcdf47882014-03-09 03:16:01 +000086 if (U.getOperandNo() == 0)
Michael Gottesman778138e2013-01-29 03:03:03 +000087 // The pointer is stored.
88 return true;
89 // The pointed is stored through.
90 continue;
91 }
92 if (isa<CallInst>(Ur))
93 // The pointer is passed as an argument, ignore this.
94 continue;
95 if (isa<PtrToIntInst>(P))
96 // Assume the worst.
97 return true;
David Blaikie70573dc2014-11-19 07:49:26 +000098 if (Visited.insert(Ur).second)
Michael Gottesman778138e2013-01-29 03:03:03 +000099 Worklist.push_back(Ur);
100 }
101 } while (!Worklist.empty());
102
103 // Everything checked out.
104 return false;
105}
106
Mehdi Aminia28d91d2015-03-10 02:37:25 +0000107bool ProvenanceAnalysis::relatedCheck(const Value *A, const Value *B,
108 const DataLayout &DL) {
Michael Gottesman778138e2013-01-29 03:03:03 +0000109 // Skip past provenance pass-throughs.
Mehdi Aminia28d91d2015-03-10 02:37:25 +0000110 A = GetUnderlyingObjCPtr(A, DL);
111 B = GetUnderlyingObjCPtr(B, DL);
Michael Gottesman778138e2013-01-29 03:03:03 +0000112
113 // Quick check.
114 if (A == B)
115 return true;
116
117 // Ask regular AliasAnalysis, for a first approximation.
118 switch (AA->alias(A, B)) {
Chandler Carruthc3f49eb2015-06-22 02:16:51 +0000119 case NoAlias:
Michael Gottesman778138e2013-01-29 03:03:03 +0000120 return false;
Chandler Carruthc3f49eb2015-06-22 02:16:51 +0000121 case MustAlias:
122 case PartialAlias:
Michael Gottesman778138e2013-01-29 03:03:03 +0000123 return true;
Chandler Carruthc3f49eb2015-06-22 02:16:51 +0000124 case MayAlias:
Michael Gottesman778138e2013-01-29 03:03:03 +0000125 break;
126 }
127
128 bool AIsIdentified = IsObjCIdentifiedObject(A);
129 bool BIsIdentified = IsObjCIdentifiedObject(B);
130
131 // An ObjC-Identified object can't alias a load if it is never locally stored.
132 if (AIsIdentified) {
133 // Check for an obvious escape.
134 if (isa<LoadInst>(B))
Michael Gottesman27029f42013-02-12 23:35:08 +0000135 return IsStoredObjCPointer(A);
Michael Gottesman778138e2013-01-29 03:03:03 +0000136 if (BIsIdentified) {
137 // Check for an obvious escape.
138 if (isa<LoadInst>(A))
Michael Gottesman27029f42013-02-12 23:35:08 +0000139 return IsStoredObjCPointer(B);
Michael Gottesman778138e2013-01-29 03:03:03 +0000140 // Both pointers are identified and escapes aren't an evident problem.
141 return false;
142 }
143 } else if (BIsIdentified) {
144 // Check for an obvious escape.
145 if (isa<LoadInst>(A))
Michael Gottesman27029f42013-02-12 23:35:08 +0000146 return IsStoredObjCPointer(B);
Michael Gottesman778138e2013-01-29 03:03:03 +0000147 }
148
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);
158
159 // Conservative.
160 return true;
161}
162
Mehdi Aminia28d91d2015-03-10 02:37:25 +0000163bool ProvenanceAnalysis::related(const Value *A, const Value *B,
164 const DataLayout &DL) {
Michael Gottesman778138e2013-01-29 03:03:03 +0000165 // 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));
171 if (!Pair.second)
172 return Pair.first->second;
173
Mehdi Aminia28d91d2015-03-10 02:37:25 +0000174 bool Result = relatedCheck(A, B, DL);
Michael Gottesman778138e2013-01-29 03:03:03 +0000175 CachedResults[ValuePairTy(A, B)] = Result;
176 return Result;
177}