Michael Gottesman | 778138e | 2013-01-29 03:03:03 +0000 | [diff] [blame] | 1 | //===- 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 Gottesman | 778138e | 2013-01-29 03:03:03 +0000 | [diff] [blame] | 27 | #include "llvm/ADT/STLExtras.h" |
Michael Gottesman | 278266f | 2013-01-29 04:20:52 +0000 | [diff] [blame] | 28 | #include "llvm/ADT/SmallPtrSet.h" |
Michael Gottesman | 778138e | 2013-01-29 03:03:03 +0000 | [diff] [blame] | 29 | |
| 30 | using namespace llvm; |
| 31 | using namespace llvm::objcarc; |
| 32 | |
| 33 | bool ProvenanceAnalysis::relatedSelect(const SelectInst *A, |
| 34 | const Value *B) { |
Mehdi Amini | a28d91d | 2015-03-10 02:37:25 +0000 | [diff] [blame] | 35 | const DataLayout &DL = A->getModule()->getDataLayout(); |
Michael Gottesman | 778138e | 2013-01-29 03:03:03 +0000 | [diff] [blame] | 36 | // 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 Amini | a28d91d | 2015-03-10 02:37:25 +0000 | [diff] [blame] | 40 | return related(A->getTrueValue(), SB->getTrueValue(), DL) || |
| 41 | related(A->getFalseValue(), SB->getFalseValue(), DL); |
Michael Gottesman | 778138e | 2013-01-29 03:03:03 +0000 | [diff] [blame] | 42 | |
| 43 | // Check both arms of the Select node individually. |
Mehdi Amini | a28d91d | 2015-03-10 02:37:25 +0000 | [diff] [blame] | 44 | return related(A->getTrueValue(), B, DL) || |
| 45 | related(A->getFalseValue(), B, DL); |
Michael Gottesman | 778138e | 2013-01-29 03:03:03 +0000 | [diff] [blame] | 46 | } |
| 47 | |
| 48 | bool ProvenanceAnalysis::relatedPHI(const PHINode *A, |
| 49 | const Value *B) { |
Mehdi Amini | a28d91d | 2015-03-10 02:37:25 +0000 | [diff] [blame] | 50 | const DataLayout &DL = A->getModule()->getDataLayout(); |
Michael Gottesman | 778138e | 2013-01-29 03:03:03 +0000 | [diff] [blame] | 51 | // 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 Amini | a28d91d | 2015-03-10 02:37:25 +0000 | [diff] [blame] | 58 | PNB->getIncomingValueForBlock(A->getIncomingBlock(i)), DL)) |
Michael Gottesman | 778138e | 2013-01-29 03:03:03 +0000 | [diff] [blame] | 59 | 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 Cooper | 833f34d | 2015-05-12 20:05:31 +0000 | [diff] [blame] | 65 | for (Value *PV1 : A->incoming_values()) { |
Mehdi Amini | a28d91d | 2015-03-10 02:37:25 +0000 | [diff] [blame] | 66 | if (UniqueSrc.insert(PV1).second && related(PV1, B, DL)) |
Michael Gottesman | 778138e | 2013-01-29 03:03:03 +0000 | [diff] [blame] | 67 | 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 Gottesman | 27029f4 | 2013-02-12 23:35:08 +0000 | [diff] [blame] | 76 | static bool IsStoredObjCPointer(const Value *P) { |
Michael Gottesman | 778138e | 2013-01-29 03:03:03 +0000 | [diff] [blame] | 77 | 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 Carruth | cdf4788 | 2014-03-09 03:16:01 +0000 | [diff] [blame] | 83 | for (const Use &U : P->uses()) { |
| 84 | const User *Ur = U.getUser(); |
Michael Gottesman | 778138e | 2013-01-29 03:03:03 +0000 | [diff] [blame] | 85 | if (isa<StoreInst>(Ur)) { |
Chandler Carruth | cdf4788 | 2014-03-09 03:16:01 +0000 | [diff] [blame] | 86 | if (U.getOperandNo() == 0) |
Michael Gottesman | 778138e | 2013-01-29 03:03:03 +0000 | [diff] [blame] | 87 | // 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 Blaikie | 70573dc | 2014-11-19 07:49:26 +0000 | [diff] [blame] | 98 | if (Visited.insert(Ur).second) |
Michael Gottesman | 778138e | 2013-01-29 03:03:03 +0000 | [diff] [blame] | 99 | Worklist.push_back(Ur); |
| 100 | } |
| 101 | } while (!Worklist.empty()); |
| 102 | |
| 103 | // Everything checked out. |
| 104 | return false; |
| 105 | } |
| 106 | |
Mehdi Amini | a28d91d | 2015-03-10 02:37:25 +0000 | [diff] [blame] | 107 | bool ProvenanceAnalysis::relatedCheck(const Value *A, const Value *B, |
| 108 | const DataLayout &DL) { |
Michael Gottesman | 778138e | 2013-01-29 03:03:03 +0000 | [diff] [blame] | 109 | // Skip past provenance pass-throughs. |
Mehdi Amini | a28d91d | 2015-03-10 02:37:25 +0000 | [diff] [blame] | 110 | A = GetUnderlyingObjCPtr(A, DL); |
| 111 | B = GetUnderlyingObjCPtr(B, DL); |
Michael Gottesman | 778138e | 2013-01-29 03:03:03 +0000 | [diff] [blame] | 112 | |
| 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 Carruth | c3f49eb | 2015-06-22 02:16:51 +0000 | [diff] [blame] | 119 | case NoAlias: |
Michael Gottesman | 778138e | 2013-01-29 03:03:03 +0000 | [diff] [blame] | 120 | return false; |
Chandler Carruth | c3f49eb | 2015-06-22 02:16:51 +0000 | [diff] [blame] | 121 | case MustAlias: |
| 122 | case PartialAlias: |
Michael Gottesman | 778138e | 2013-01-29 03:03:03 +0000 | [diff] [blame] | 123 | return true; |
Chandler Carruth | c3f49eb | 2015-06-22 02:16:51 +0000 | [diff] [blame] | 124 | case MayAlias: |
Michael Gottesman | 778138e | 2013-01-29 03:03:03 +0000 | [diff] [blame] | 125 | 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 Gottesman | 27029f4 | 2013-02-12 23:35:08 +0000 | [diff] [blame] | 135 | return IsStoredObjCPointer(A); |
Michael Gottesman | 778138e | 2013-01-29 03:03:03 +0000 | [diff] [blame] | 136 | if (BIsIdentified) { |
| 137 | // Check for an obvious escape. |
| 138 | if (isa<LoadInst>(A)) |
Michael Gottesman | 27029f4 | 2013-02-12 23:35:08 +0000 | [diff] [blame] | 139 | return IsStoredObjCPointer(B); |
Michael Gottesman | 778138e | 2013-01-29 03:03:03 +0000 | [diff] [blame] | 140 | // 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 Gottesman | 27029f4 | 2013-02-12 23:35:08 +0000 | [diff] [blame] | 146 | return IsStoredObjCPointer(B); |
Michael Gottesman | 778138e | 2013-01-29 03:03:03 +0000 | [diff] [blame] | 147 | } |
| 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 Amini | a28d91d | 2015-03-10 02:37:25 +0000 | [diff] [blame] | 163 | bool ProvenanceAnalysis::related(const Value *A, const Value *B, |
| 164 | const DataLayout &DL) { |
Michael Gottesman | 778138e | 2013-01-29 03:03:03 +0000 | [diff] [blame] | 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)); |
| 171 | if (!Pair.second) |
| 172 | return Pair.first->second; |
| 173 | |
Mehdi Amini | a28d91d | 2015-03-10 02:37:25 +0000 | [diff] [blame] | 174 | bool Result = relatedCheck(A, B, DL); |
Michael Gottesman | 778138e | 2013-01-29 03:03:03 +0000 | [diff] [blame] | 175 | CachedResults[ValuePairTy(A, B)] = Result; |
| 176 | return Result; |
| 177 | } |