/tmp/buildd/llvm-toolchain-snapshot-3.6~svn224456/lib/Analysis/MemoryDependenceAnalysis.cpp

Bug Summary

File:	lib/Analysis/MemoryDependenceAnalysis.cpp
Location:	line 1148, column 9
Description:	Value stored to 'NumSortedEntries' is never read

Annotated Source Code

1	//===- MemoryDependenceAnalysis.cpp - Mem Deps Implementation -------------===//
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	//
10	// This file implements an analysis that determines, for a given memory
11	// operation, what preceding memory operations it depends on. It builds on
12	// alias analysis information, and tries to provide a lazy, caching interface to
13	// a common kind of alias information query.
14	//
15	//===----------------------------------------------------------------------===//
16
17	#include "llvm/Analysis/MemoryDependenceAnalysis.h"
18	#include "llvm/ADT/STLExtras.h"
19	#include "llvm/ADT/Statistic.h"
20	#include "llvm/Analysis/AliasAnalysis.h"
21	#include "llvm/Analysis/AssumptionTracker.h"
22	#include "llvm/Analysis/InstructionSimplify.h"
23	#include "llvm/Analysis/MemoryBuiltins.h"
24	#include "llvm/Analysis/PHITransAddr.h"
25	#include "llvm/Analysis/ValueTracking.h"
26	#include "llvm/IR/DataLayout.h"
27	#include "llvm/IR/Dominators.h"
28	#include "llvm/IR/Function.h"
29	#include "llvm/IR/Instructions.h"
30	#include "llvm/IR/IntrinsicInst.h"
31	#include "llvm/IR/LLVMContext.h"
32	#include "llvm/IR/PredIteratorCache.h"
33	#include "llvm/Support/Debug.h"
34	using namespace llvm;
35
36	#define DEBUG_TYPE"memdep" "memdep"
37
38	STATISTIC(NumCacheNonLocal, "Number of fully cached non-local responses")static llvm::Statistic NumCacheNonLocal = { "memdep", "Number of fully cached non-local responses" , 0, 0 };
39	STATISTIC(NumCacheDirtyNonLocal, "Number of dirty cached non-local responses")static llvm::Statistic NumCacheDirtyNonLocal = { "memdep", "Number of dirty cached non-local responses" , 0, 0 };
40	STATISTIC(NumUncacheNonLocal, "Number of uncached non-local responses")static llvm::Statistic NumUncacheNonLocal = { "memdep", "Number of uncached non-local responses" , 0, 0 };
41
42	STATISTIC(NumCacheNonLocalPtr,static llvm::Statistic NumCacheNonLocalPtr = { "memdep", "Number of fully cached non-local ptr responses" , 0, 0 }
43	"Number of fully cached non-local ptr responses")static llvm::Statistic NumCacheNonLocalPtr = { "memdep", "Number of fully cached non-local ptr responses" , 0, 0 };
44	STATISTIC(NumCacheDirtyNonLocalPtr,static llvm::Statistic NumCacheDirtyNonLocalPtr = { "memdep", "Number of cached, but dirty, non-local ptr responses", 0, 0 }
45	"Number of cached, but dirty, non-local ptr responses")static llvm::Statistic NumCacheDirtyNonLocalPtr = { "memdep", "Number of cached, but dirty, non-local ptr responses", 0, 0 };
46	STATISTIC(NumUncacheNonLocalPtr,static llvm::Statistic NumUncacheNonLocalPtr = { "memdep", "Number of uncached non-local ptr responses" , 0, 0 }
47	"Number of uncached non-local ptr responses")static llvm::Statistic NumUncacheNonLocalPtr = { "memdep", "Number of uncached non-local ptr responses" , 0, 0 };
48	STATISTIC(NumCacheCompleteNonLocalPtr,static llvm::Statistic NumCacheCompleteNonLocalPtr = { "memdep" , "Number of block queries that were completely cached", 0, 0 }
49	"Number of block queries that were completely cached")static llvm::Statistic NumCacheCompleteNonLocalPtr = { "memdep" , "Number of block queries that were completely cached", 0, 0 };
50
51	// Limit for the number of instructions to scan in a block.
52	static const unsigned int BlockScanLimit = 100;
53
54	// Limit on the number of memdep results to process.
55	static const unsigned int NumResultsLimit = 100;
56
57	char MemoryDependenceAnalysis::ID = 0;
58
59	// Register this pass...
60	INITIALIZE_PASS_BEGIN(MemoryDependenceAnalysis, "memdep",static void* initializeMemoryDependenceAnalysisPassOnce(PassRegistry &Registry) {
61	"Memory Dependence Analysis", false, true)static void* initializeMemoryDependenceAnalysisPassOnce(PassRegistry &Registry) {
62	INITIALIZE_PASS_DEPENDENCY(AssumptionTracker)initializeAssumptionTrackerPass(Registry);
63	INITIALIZE_AG_DEPENDENCY(AliasAnalysis)initializeAliasAnalysisAnalysisGroup(Registry);
64	INITIALIZE_PASS_END(MemoryDependenceAnalysis, "memdep",PassInfo PI = new PassInfo("Memory Dependence Analysis", "memdep" , & MemoryDependenceAnalysis ::ID, PassInfo::NormalCtor_t (callDefaultCtor< MemoryDependenceAnalysis >), false, true ); Registry.registerPass(PI, true); return PI; } void llvm:: initializeMemoryDependenceAnalysisPass(PassRegistry &Registry ) { static volatile sys::cas_flag initialized = 0; sys::cas_flag old_val = sys::CompareAndSwap(&initialized, 1, 0); if (old_val == 0) { initializeMemoryDependenceAnalysisPassOnce(Registry) ; sys::MemoryFence(); AnnotateIgnoreWritesBegin("/tmp/buildd/llvm-toolchain-snapshot-3.6~svn224456/lib/Analysis/MemoryDependenceAnalysis.cpp" , 65); AnnotateHappensBefore("/tmp/buildd/llvm-toolchain-snapshot-3.6~svn224456/lib/Analysis/MemoryDependenceAnalysis.cpp" , 65, &initialized); initialized = 2; AnnotateIgnoreWritesEnd ("/tmp/buildd/llvm-toolchain-snapshot-3.6~svn224456/lib/Analysis/MemoryDependenceAnalysis.cpp" , 65); } else { sys::cas_flag tmp = initialized; sys::MemoryFence (); while (tmp != 2) { tmp = initialized; sys::MemoryFence(); } } AnnotateHappensAfter("/tmp/buildd/llvm-toolchain-snapshot-3.6~svn224456/lib/Analysis/MemoryDependenceAnalysis.cpp" , 65, &initialized); }
65	"Memory Dependence Analysis", false, true)PassInfo PI = new PassInfo("Memory Dependence Analysis", "memdep" , & MemoryDependenceAnalysis ::ID, PassInfo::NormalCtor_t (callDefaultCtor< MemoryDependenceAnalysis >), false, true ); Registry.registerPass(PI, true); return PI; } void llvm:: initializeMemoryDependenceAnalysisPass(PassRegistry &Registry ) { static volatile sys::cas_flag initialized = 0; sys::cas_flag old_val = sys::CompareAndSwap(&initialized, 1, 0); if (old_val == 0) { initializeMemoryDependenceAnalysisPassOnce(Registry) ; sys::MemoryFence(); AnnotateIgnoreWritesBegin("/tmp/buildd/llvm-toolchain-snapshot-3.6~svn224456/lib/Analysis/MemoryDependenceAnalysis.cpp" , 65); AnnotateHappensBefore("/tmp/buildd/llvm-toolchain-snapshot-3.6~svn224456/lib/Analysis/MemoryDependenceAnalysis.cpp" , 65, &initialized); initialized = 2; AnnotateIgnoreWritesEnd ("/tmp/buildd/llvm-toolchain-snapshot-3.6~svn224456/lib/Analysis/MemoryDependenceAnalysis.cpp" , 65); } else { sys::cas_flag tmp = initialized; sys::MemoryFence (); while (tmp != 2) { tmp = initialized; sys::MemoryFence(); } } AnnotateHappensAfter("/tmp/buildd/llvm-toolchain-snapshot-3.6~svn224456/lib/Analysis/MemoryDependenceAnalysis.cpp" , 65, &initialized); }
66
67	MemoryDependenceAnalysis::MemoryDependenceAnalysis()
68	: FunctionPass(ID), PredCache() {
69	initializeMemoryDependenceAnalysisPass(*PassRegistry::getPassRegistry());
70	}
71	MemoryDependenceAnalysis::~MemoryDependenceAnalysis() {
72	}
73
74	/// Clean up memory in between runs
75	void MemoryDependenceAnalysis::releaseMemory() {
76	LocalDeps.clear();
77	NonLocalDeps.clear();
78	NonLocalPointerDeps.clear();
79	ReverseLocalDeps.clear();
80	ReverseNonLocalDeps.clear();
81	ReverseNonLocalPtrDeps.clear();
82	PredCache->clear();
83	}
84
85
86
87	/// getAnalysisUsage - Does not modify anything. It uses Alias Analysis.
88	///
89	void MemoryDependenceAnalysis::getAnalysisUsage(AnalysisUsage &AU) const {
90	AU.setPreservesAll();
91	AU.addRequired<AssumptionTracker>();
92	AU.addRequiredTransitive<AliasAnalysis>();
93	}
94
95	bool MemoryDependenceAnalysis::runOnFunction(Function &) {
96	AA = &getAnalysis<AliasAnalysis>();
97	AT = &getAnalysis<AssumptionTracker>();
98	DataLayoutPass *DLP = getAnalysisIfAvailable<DataLayoutPass>();
99	DL = DLP ? &DLP->getDataLayout() : nullptr;
100	DominatorTreeWrapperPass *DTWP =
101	getAnalysisIfAvailable<DominatorTreeWrapperPass>();
102	DT = DTWP ? &DTWP->getDomTree() : nullptr;
103	if (!PredCache)
104	PredCache.reset(new PredIteratorCache());
105	return false;
106	}
107
108	/// RemoveFromReverseMap - This is a helper function that removes Val from
109	/// 'Inst's set in ReverseMap. If the set becomes empty, remove Inst's entry.
110	template <typename KeyTy>
111	static void RemoveFromReverseMap(DenseMap<Instruction*,
112	SmallPtrSet<KeyTy, 4> > &ReverseMap,
113	Instruction *Inst, KeyTy Val) {
114	typename DenseMap<Instruction*, SmallPtrSet<KeyTy, 4> >::iterator
115	InstIt = ReverseMap.find(Inst);
116	assert(InstIt != ReverseMap.end() && "Reverse map out of sync?")((InstIt != ReverseMap.end() && "Reverse map out of sync?" ) ? static_cast<void> (0) : __assert_fail ("InstIt != ReverseMap.end() && \"Reverse map out of sync?\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.6~svn224456/lib/Analysis/MemoryDependenceAnalysis.cpp" , 116, __PRETTY_FUNCTION__));
117	bool Found = InstIt->second.erase(Val);
118	assert(Found && "Invalid reverse map!")((Found && "Invalid reverse map!") ? static_cast<void > (0) : __assert_fail ("Found && \"Invalid reverse map!\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.6~svn224456/lib/Analysis/MemoryDependenceAnalysis.cpp" , 118, __PRETTY_FUNCTION__)); (void)Found;
119	if (InstIt->second.empty())
120	ReverseMap.erase(InstIt);
121	}
122
123	/// GetLocation - If the given instruction references a specific memory
124	/// location, fill in Loc with the details, otherwise set Loc.Ptr to null.
125	/// Return a ModRefInfo value describing the general behavior of the
126	/// instruction.
127	static
128	AliasAnalysis::ModRefResult GetLocation(const Instruction *Inst,
129	AliasAnalysis::Location &Loc,
130	AliasAnalysis *AA) {
131	if (const LoadInst *LI = dyn_cast<LoadInst>(Inst)) {
132	if (LI->isUnordered()) {
133	Loc = AA->getLocation(LI);
134	return AliasAnalysis::Ref;
135	}
136	if (LI->getOrdering() == Monotonic) {
137	Loc = AA->getLocation(LI);
138	return AliasAnalysis::ModRef;
139	}
140	Loc = AliasAnalysis::Location();
141	return AliasAnalysis::ModRef;
142	}
143
144	if (const StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
145	if (SI->isUnordered()) {
146	Loc = AA->getLocation(SI);
147	return AliasAnalysis::Mod;
148	}
149	if (SI->getOrdering() == Monotonic) {
150	Loc = AA->getLocation(SI);
151	return AliasAnalysis::ModRef;
152	}
153	Loc = AliasAnalysis::Location();
154	return AliasAnalysis::ModRef;
155	}
156
157	if (const VAArgInst *V = dyn_cast<VAArgInst>(Inst)) {
158	Loc = AA->getLocation(V);
159	return AliasAnalysis::ModRef;
160	}
161
162	if (const CallInst *CI = isFreeCall(Inst, AA->getTargetLibraryInfo())) {
163	// calls to free() deallocate the entire structure
164	Loc = AliasAnalysis::Location(CI->getArgOperand(0));
165	return AliasAnalysis::Mod;
166	}
167
168	if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst)) {
169	AAMDNodes AAInfo;
170
171	switch (II->getIntrinsicID()) {
172	case Intrinsic::lifetime_start:
173	case Intrinsic::lifetime_end:
174	case Intrinsic::invariant_start:
175	II->getAAMetadata(AAInfo);
176	Loc = AliasAnalysis::Location(II->getArgOperand(1),
177	cast<ConstantInt>(II->getArgOperand(0))
178	->getZExtValue(), AAInfo);
179	// These intrinsics don't really modify the memory, but returning Mod
180	// will allow them to be handled conservatively.
181	return AliasAnalysis::Mod;
182	case Intrinsic::invariant_end:
183	II->getAAMetadata(AAInfo);
184	Loc = AliasAnalysis::Location(II->getArgOperand(2),
185	cast<ConstantInt>(II->getArgOperand(1))
186	->getZExtValue(), AAInfo);
187	// These intrinsics don't really modify the memory, but returning Mod
188	// will allow them to be handled conservatively.
189	return AliasAnalysis::Mod;
190	default:
191	break;
192	}
193	}
194
195	// Otherwise, just do the coarse-grained thing that always works.
196	if (Inst->mayWriteToMemory())
197	return AliasAnalysis::ModRef;
198	if (Inst->mayReadFromMemory())
199	return AliasAnalysis::Ref;
200	return AliasAnalysis::NoModRef;
201	}
202
203	/// getCallSiteDependencyFrom - Private helper for finding the local
204	/// dependencies of a call site.
205	MemDepResult MemoryDependenceAnalysis::
206	getCallSiteDependencyFrom(CallSite CS, bool isReadOnlyCall,
207	BasicBlock::iterator ScanIt, BasicBlock *BB) {
208	unsigned Limit = BlockScanLimit;
209
210	// Walk backwards through the block, looking for dependencies
211	while (ScanIt != BB->begin()) {
212	// Limit the amount of scanning we do so we don't end up with quadratic
213	// running time on extreme testcases.
214	--Limit;
215	if (!Limit)
216	return MemDepResult::getUnknown();
217
218	Instruction *Inst = --ScanIt;
219
220	// If this inst is a memory op, get the pointer it accessed
221	AliasAnalysis::Location Loc;
222	AliasAnalysis::ModRefResult MR = GetLocation(Inst, Loc, AA);
223	if (Loc.Ptr) {
224	// A simple instruction.
225	if (AA->getModRefInfo(CS, Loc) != AliasAnalysis::NoModRef)
226	return MemDepResult::getClobber(Inst);
227	continue;
228	}
229
230	if (CallSite InstCS = cast<Value>(Inst)) {
231	// Debug intrinsics don't cause dependences.
232	if (isa<DbgInfoIntrinsic>(Inst)) continue;
233	// If these two calls do not interfere, look past it.
234	switch (AA->getModRefInfo(CS, InstCS)) {
235	case AliasAnalysis::NoModRef:
236	// If the two calls are the same, return InstCS as a Def, so that
237	// CS can be found redundant and eliminated.
238	if (isReadOnlyCall && !(MR & AliasAnalysis::Mod) &&
239	CS.getInstruction()->isIdenticalToWhenDefined(Inst))
240	return MemDepResult::getDef(Inst);
241
242	// Otherwise if the two calls don't interact (e.g. InstCS is readnone)
243	// keep scanning.
244	continue;
245	default:
246	return MemDepResult::getClobber(Inst);
247	}
248	}
249
250	// If we could not obtain a pointer for the instruction and the instruction
251	// touches memory then assume that this is a dependency.
252	if (MR != AliasAnalysis::NoModRef)
253	return MemDepResult::getClobber(Inst);
254	}
255
256	// No dependence found. If this is the entry block of the function, it is
257	// unknown, otherwise it is non-local.
258	if (BB != &BB->getParent()->getEntryBlock())
259	return MemDepResult::getNonLocal();
260	return MemDepResult::getNonFuncLocal();
261	}
262
263	/// isLoadLoadClobberIfExtendedToFullWidth - Return true if LI is a load that
264	/// would fully overlap MemLoc if done as a wider legal integer load.
265	///
266	/// MemLocBase, MemLocOffset are lazily computed here the first time the
267	/// base/offs of memloc is needed.
268	static bool
269	isLoadLoadClobberIfExtendedToFullWidth(const AliasAnalysis::Location &MemLoc,
270	const Value *&MemLocBase,
271	int64_t &MemLocOffs,
272	const LoadInst *LI,
273	const DataLayout *DL) {
274	// If we have no target data, we can't do this.
275	if (!DL) return false;
276
277	// If we haven't already computed the base/offset of MemLoc, do so now.
278	if (!MemLocBase)
279	MemLocBase = GetPointerBaseWithConstantOffset(MemLoc.Ptr, MemLocOffs, DL);
280
281	unsigned Size = MemoryDependenceAnalysis::
282	getLoadLoadClobberFullWidthSize(MemLocBase, MemLocOffs, MemLoc.Size,
283	LI, *DL);
284	return Size != 0;
285	}
286
287	/// getLoadLoadClobberFullWidthSize - This is a little bit of analysis that
288	/// looks at a memory location for a load (specified by MemLocBase, Offs,
289	/// and Size) and compares it against a load. If the specified load could
290	/// be safely widened to a larger integer load that is 1) still efficient,
291	/// 2) safe for the target, and 3) would provide the specified memory
292	/// location value, then this function returns the size in bytes of the
293	/// load width to use. If not, this returns zero.
294	unsigned MemoryDependenceAnalysis::
295	getLoadLoadClobberFullWidthSize(const Value *MemLocBase, int64_t MemLocOffs,
296	unsigned MemLocSize, const LoadInst *LI,
297	const DataLayout &DL) {
298	// We can only extend simple integer loads.
299	if (!isa<IntegerType>(LI->getType()) \|\| !LI->isSimple()) return 0;
300
301	// Load widening is hostile to ThreadSanitizer: it may cause false positives
302	// or make the reports more cryptic (access sizes are wrong).
303	if (LI->getParent()->getParent()->getAttributes().
304	hasAttribute(AttributeSet::FunctionIndex, Attribute::SanitizeThread))
305	return 0;
306
307	// Get the base of this load.
308	int64_t LIOffs = 0;
309	const Value *LIBase =
310	GetPointerBaseWithConstantOffset(LI->getPointerOperand(), LIOffs, &DL);
311
312	// If the two pointers are not based on the same pointer, we can't tell that
313	// they are related.
314	if (LIBase != MemLocBase) return 0;
315
316	// Okay, the two values are based on the same pointer, but returned as
317	// no-alias. This happens when we have things like two byte loads at "P+1"
318	// and "P+3". Check to see if increasing the size of the "LI" load up to its
319	// alignment (or the largest native integer type) will allow us to load all
320	// the bits required by MemLoc.
321
322	// If MemLoc is before LI, then no widening of LI will help us out.
323	if (MemLocOffs < LIOffs) return 0;
324
325	// Get the alignment of the load in bytes. We assume that it is safe to load
326	// any legal integer up to this size without a problem. For example, if we're
327	// looking at an i8 load on x86-32 that is known 1024 byte aligned, we can
328	// widen it up to an i32 load. If it is known 2-byte aligned, we can widen it
329	// to i16.
330	unsigned LoadAlign = LI->getAlignment();
331
332	int64_t MemLocEnd = MemLocOffs+MemLocSize;
333
334	// If no amount of rounding up will let MemLoc fit into LI, then bail out.
335	if (LIOffs+LoadAlign < MemLocEnd) return 0;
336
337	// This is the size of the load to try. Start with the next larger power of
338	// two.
339	unsigned NewLoadByteSize = LI->getType()->getPrimitiveSizeInBits()/8U;
340	NewLoadByteSize = NextPowerOf2(NewLoadByteSize);
341
342	while (1) {
343	// If this load size is bigger than our known alignment or would not fit
344	// into a native integer register, then we fail.
345	if (NewLoadByteSize > LoadAlign \|\|
346	!DL.fitsInLegalInteger(NewLoadByteSize*8))
347	return 0;
348
349	if (LIOffs+NewLoadByteSize > MemLocEnd &&
350	LI->getParent()->getParent()->getAttributes().
351	hasAttribute(AttributeSet::FunctionIndex, Attribute::SanitizeAddress))
352	// We will be reading past the location accessed by the original program.
353	// While this is safe in a regular build, Address Safety analysis tools
354	// may start reporting false warnings. So, don't do widening.
355	return 0;
356
357	// If a load of this width would include all of MemLoc, then we succeed.
358	if (LIOffs+NewLoadByteSize >= MemLocEnd)
359	return NewLoadByteSize;
360
361	NewLoadByteSize <<= 1;
362	}
363	}
364
365	/// getPointerDependencyFrom - Return the instruction on which a memory
366	/// location depends. If isLoad is true, this routine ignores may-aliases with
367	/// read-only operations. If isLoad is false, this routine ignores may-aliases
368	/// with reads from read-only locations. If possible, pass the query
369	/// instruction as well; this function may take advantage of the metadata
370	/// annotated to the query instruction to refine the result.
371	MemDepResult MemoryDependenceAnalysis::
372	getPointerDependencyFrom(const AliasAnalysis::Location &MemLoc, bool isLoad,
373	BasicBlock::iterator ScanIt, BasicBlock *BB,
374	Instruction *QueryInst) {
375
376	const Value *MemLocBase = nullptr;
377	int64_t MemLocOffset = 0;
378	unsigned Limit = BlockScanLimit;
379	bool isInvariantLoad = false;
380
381	// We must be careful with atomic accesses, as they may allow another thread
382	// to touch this location, cloberring it. We are conservative: if the
383	// QueryInst is not a simple (non-atomic) memory access, we automatically
384	// return getClobber.
385	// If it is simple, we know based on the results of
386	// "Compiler testing via a theory of sound optimisations in the C11/C++11
387	// memory model" in PLDI 2013, that a non-atomic location can only be
388	// clobbered between a pair of a release and an acquire action, with no
389	// access to the location in between.
390	// Here is an example for giving the general intuition behind this rule.
391	// In the following code:
392	// store x 0;
393	// release action; [1]
394	// acquire action; [4]
395	// %val = load x;
396	// It is unsafe to replace %val by 0 because another thread may be running:
397	// acquire action; [2]
398	// store x 42;
399	// release action; [3]
400	// with synchronization from 1 to 2 and from 3 to 4, resulting in %val
401	// being 42. A key property of this program however is that if either
402	// 1 or 4 were missing, there would be a race between the store of 42
403	// either the store of 0 or the load (making the whole progam racy).
404	// The paper mentionned above shows that the same property is respected
405	// by every program that can detect any optimisation of that kind: either
406	// it is racy (undefined) or there is a release followed by an acquire
407	// between the pair of accesses under consideration.
408	bool HasSeenAcquire = false;
409
410	if (isLoad && QueryInst) {
411	LoadInst *LI = dyn_cast<LoadInst>(QueryInst);
412	if (LI && LI->getMetadata(LLVMContext::MD_invariant_load) != nullptr)
413	isInvariantLoad = true;
414	}
415
416	// Walk backwards through the basic block, looking for dependencies.
417	while (ScanIt != BB->begin()) {
418	Instruction *Inst = --ScanIt;
419
420	if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst))
421	// Debug intrinsics don't (and can't) cause dependencies.
422	if (isa<DbgInfoIntrinsic>(II)) continue;
423
424	// Limit the amount of scanning we do so we don't end up with quadratic
425	// running time on extreme testcases.
426	--Limit;
427	if (!Limit)
428	return MemDepResult::getUnknown();
429
430	if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst)) {
431	// If we reach a lifetime begin or end marker, then the query ends here
432	// because the value is undefined.
433	if (II->getIntrinsicID() == Intrinsic::lifetime_start) {
434	// FIXME: This only considers queries directly on the invariant-tagged
435	// pointer, not on query pointers that are indexed off of them. It'd
436	// be nice to handle that at some point (the right approach is to use
437	// GetPointerBaseWithConstantOffset).
438	if (AA->isMustAlias(AliasAnalysis::Location(II->getArgOperand(1)),
439	MemLoc))
440	return MemDepResult::getDef(II);
441	continue;
442	}
443	}
444
445	// Values depend on loads if the pointers are must aliased. This means that
446	// a load depends on another must aliased load from the same value.
447	// One exception is atomic loads: a value can depend on an atomic load that it
448	// does not alias with when this atomic load indicates that another thread may
449	// be accessing the location.
450	if (LoadInst *LI = dyn_cast<LoadInst>(Inst)) {
451	// Atomic loads have complications involved.
452	// A Monotonic (or higher) load is OK if the query inst is itself not atomic.
453	// An Acquire (or higher) load sets the HasSeenAcquire flag, so that any
454	// release store will know to return getClobber.
455	// FIXME: This is overly conservative.
456	if (!LI->isUnordered()) {
457	if (!QueryInst)
458	return MemDepResult::getClobber(LI);
459	if (auto *QueryLI = dyn_cast<LoadInst>(QueryInst)) {
460	if (!QueryLI->isSimple())
461	return MemDepResult::getClobber(LI);
462	} else if (auto *QuerySI = dyn_cast<StoreInst>(QueryInst)) {
463	if (!QuerySI->isSimple())
464	return MemDepResult::getClobber(LI);
465	} else if (QueryInst->mayReadOrWriteMemory()) {
466	return MemDepResult::getClobber(LI);
467	}
468
469	if (isAtLeastAcquire(LI->getOrdering()))
470	HasSeenAcquire = true;
471	}
472
473	// FIXME: this is overly conservative.
474	// While volatile access cannot be eliminated, they do not have to clobber
475	// non-aliasing locations, as normal accesses can for example be reordered
476	// with volatile accesses.
477	if (LI->isVolatile())
478	return MemDepResult::getClobber(LI);
479
480	AliasAnalysis::Location LoadLoc = AA->getLocation(LI);
481
482	// If we found a pointer, check if it could be the same as our pointer.
483	AliasAnalysis::AliasResult R = AA->alias(LoadLoc, MemLoc);
484
485	if (isLoad) {
486	if (R == AliasAnalysis::NoAlias) {
487	// If this is an over-aligned integer load (for example,
488	// "load i8* %P, align 4") see if it would obviously overlap with the
489	// queried location if widened to a larger load (e.g. if the queried
490	// location is 1 byte at P+1). If so, return it as a load/load
491	// clobber result, allowing the client to decide to widen the load if
492	// it wants to.
493	if (IntegerType *ITy = dyn_cast<IntegerType>(LI->getType()))
494	if (LI->getAlignment()*8 > ITy->getPrimitiveSizeInBits() &&
495	isLoadLoadClobberIfExtendedToFullWidth(MemLoc, MemLocBase,
496	MemLocOffset, LI, DL))
497	return MemDepResult::getClobber(Inst);
498
499	continue;
500	}
501
502	// Must aliased loads are defs of each other.
503	if (R == AliasAnalysis::MustAlias)
504	return MemDepResult::getDef(Inst);
505
506	#if 0 // FIXME: Temporarily disabled. GVN is cleverly rewriting loads
507	// in terms of clobbering loads, but since it does this by looking
508	// at the clobbering load directly, it doesn't know about any
509	// phi translation that may have happened along the way.
510
511	// If we have a partial alias, then return this as a clobber for the
512	// client to handle.
513	if (R == AliasAnalysis::PartialAlias)
514	return MemDepResult::getClobber(Inst);
515	#endif
516
517	// Random may-alias loads don't depend on each other without a
518	// dependence.
519	continue;
520	}
521
522	// Stores don't depend on other no-aliased accesses.
523	if (R == AliasAnalysis::NoAlias)
524	continue;
525
526	// Stores don't alias loads from read-only memory.
527	if (AA->pointsToConstantMemory(LoadLoc))
528	continue;
529
530	// Stores depend on may/must aliased loads.
531	return MemDepResult::getDef(Inst);
532	}
533
534	if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
535	// Atomic stores have complications involved.
536	// A Monotonic store is OK if the query inst is itself not atomic.
537	// A Release (or higher) store further requires that no acquire load
538	// has been seen.
539	// FIXME: This is overly conservative.
540	if (!SI->isUnordered()) {
541	if (!QueryInst)
542	return MemDepResult::getClobber(SI);
543	if (auto *QueryLI = dyn_cast<LoadInst>(QueryInst)) {
544	if (!QueryLI->isSimple())
545	return MemDepResult::getClobber(SI);
546	} else if (auto *QuerySI = dyn_cast<StoreInst>(QueryInst)) {
547	if (!QuerySI->isSimple())
548	return MemDepResult::getClobber(SI);
549	} else if (QueryInst->mayReadOrWriteMemory()) {
550	return MemDepResult::getClobber(SI);
551	}
552
553	if (HasSeenAcquire && isAtLeastRelease(SI->getOrdering()))
554	return MemDepResult::getClobber(SI);
555	}
556
557	// FIXME: this is overly conservative.
558	// While volatile access cannot be eliminated, they do not have to clobber
559	// non-aliasing locations, as normal accesses can for example be reordered
560	// with volatile accesses.
561	if (SI->isVolatile())
562	return MemDepResult::getClobber(SI);
563
564	// If alias analysis can tell that this store is guaranteed to not modify
565	// the query pointer, ignore it. Use getModRefInfo to handle cases where
566	// the query pointer points to constant memory etc.
567	if (AA->getModRefInfo(SI, MemLoc) == AliasAnalysis::NoModRef)
568	continue;
569
570	// Ok, this store might clobber the query pointer. Check to see if it is
571	// a must alias: in this case, we want to return this as a def.
572	AliasAnalysis::Location StoreLoc = AA->getLocation(SI);
573
574	// If we found a pointer, check if it could be the same as our pointer.
575	AliasAnalysis::AliasResult R = AA->alias(StoreLoc, MemLoc);
576
577	if (R == AliasAnalysis::NoAlias)
578	continue;
579	if (R == AliasAnalysis::MustAlias)
580	return MemDepResult::getDef(Inst);
581	if (isInvariantLoad)
582	continue;
583	return MemDepResult::getClobber(Inst);
584	}
585
586	// If this is an allocation, and if we know that the accessed pointer is to
587	// the allocation, return Def. This means that there is no dependence and
588	// the access can be optimized based on that. For example, a load could
589	// turn into undef.
590	// Note: Only determine this to be a malloc if Inst is the malloc call, not
591	// a subsequent bitcast of the malloc call result. There can be stores to
592	// the malloced memory between the malloc call and its bitcast uses, and we
593	// need to continue scanning until the malloc call.
594	const TargetLibraryInfo *TLI = AA->getTargetLibraryInfo();
595	if (isa<AllocaInst>(Inst) \|\| isNoAliasFn(Inst, TLI)) {
596	const Value *AccessPtr = GetUnderlyingObject(MemLoc.Ptr, DL);
597
598	if (AccessPtr == Inst \|\| AA->isMustAlias(Inst, AccessPtr))
599	return MemDepResult::getDef(Inst);
600	// Be conservative if the accessed pointer may alias the allocation.
601	if (AA->alias(Inst, AccessPtr) != AliasAnalysis::NoAlias)
602	return MemDepResult::getClobber(Inst);
603	// If the allocation is not aliased and does not read memory (like
604	// strdup), it is safe to ignore.
605	if (isa<AllocaInst>(Inst) \|\|
606	isMallocLikeFn(Inst, TLI) \|\| isCallocLikeFn(Inst, TLI))
607	continue;
608	}
609
610	// See if this instruction (e.g. a call or vaarg) mod/ref's the pointer.
611	AliasAnalysis::ModRefResult MR = AA->getModRefInfo(Inst, MemLoc);
612	// If necessary, perform additional analysis.
613	if (MR == AliasAnalysis::ModRef)
614	MR = AA->callCapturesBefore(Inst, MemLoc, DT);
615	switch (MR) {
616	case AliasAnalysis::NoModRef:
617	// If the call has no effect on the queried pointer, just ignore it.
618	continue;
619	case AliasAnalysis::Mod:
620	return MemDepResult::getClobber(Inst);
621	case AliasAnalysis::Ref:
622	// If the call is known to never store to the pointer, and if this is a
623	// load query, we can safely ignore it (scan past it).
624	if (isLoad)
625	continue;
626	default:
627	// Otherwise, there is a potential dependence. Return a clobber.
628	return MemDepResult::getClobber(Inst);
629	}
630	}
631
632	// No dependence found. If this is the entry block of the function, it is
633	// unknown, otherwise it is non-local.
634	if (BB != &BB->getParent()->getEntryBlock())
635	return MemDepResult::getNonLocal();
636	return MemDepResult::getNonFuncLocal();
637	}
638
639	/// getDependency - Return the instruction on which a memory operation
640	/// depends.
641	MemDepResult MemoryDependenceAnalysis::getDependency(Instruction *QueryInst) {
642	Instruction *ScanPos = QueryInst;
643
644	// Check for a cached result
645	MemDepResult &LocalCache = LocalDeps[QueryInst];
646
647	// If the cached entry is non-dirty, just return it. Note that this depends
648	// on MemDepResult's default constructing to 'dirty'.
649	if (!LocalCache.isDirty())
650	return LocalCache;
651
652	// Otherwise, if we have a dirty entry, we know we can start the scan at that
653	// instruction, which may save us some work.
654	if (Instruction *Inst = LocalCache.getInst()) {
655	ScanPos = Inst;
656
657	RemoveFromReverseMap(ReverseLocalDeps, Inst, QueryInst);
658	}
659
660	BasicBlock *QueryParent = QueryInst->getParent();
661
662	// Do the scan.
663	if (BasicBlock::iterator(QueryInst) == QueryParent->begin()) {
664	// No dependence found. If this is the entry block of the function, it is
665	// unknown, otherwise it is non-local.
666	if (QueryParent != &QueryParent->getParent()->getEntryBlock())
667	LocalCache = MemDepResult::getNonLocal();
668	else
669	LocalCache = MemDepResult::getNonFuncLocal();
670	} else {
671	AliasAnalysis::Location MemLoc;
672	AliasAnalysis::ModRefResult MR = GetLocation(QueryInst, MemLoc, AA);
673	if (MemLoc.Ptr) {
674	// If we can do a pointer scan, make it happen.
675	bool isLoad = !(MR & AliasAnalysis::Mod);
676	if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(QueryInst))
677	isLoad \|= II->getIntrinsicID() == Intrinsic::lifetime_start;
678
679	LocalCache = getPointerDependencyFrom(MemLoc, isLoad, ScanPos,
680	QueryParent, QueryInst);
681	} else if (isa<CallInst>(QueryInst) \|\| isa<InvokeInst>(QueryInst)) {
682	CallSite QueryCS(QueryInst);
683	bool isReadOnly = AA->onlyReadsMemory(QueryCS);
684	LocalCache = getCallSiteDependencyFrom(QueryCS, isReadOnly, ScanPos,
685	QueryParent);
686	} else
687	// Non-memory instruction.
688	LocalCache = MemDepResult::getUnknown();
689	}
690
691	// Remember the result!
692	if (Instruction *I = LocalCache.getInst())
693	ReverseLocalDeps[I].insert(QueryInst);
694
695	return LocalCache;
696	}
697
698	#ifndef NDEBUG
699	/// AssertSorted - This method is used when -debug is specified to verify that
700	/// cache arrays are properly kept sorted.
701	static void AssertSorted(MemoryDependenceAnalysis::NonLocalDepInfo &Cache,
702	int Count = -1) {
703	if (Count == -1) Count = Cache.size();
704	if (Count == 0) return;
705
706	for (unsigned i = 1; i != unsigned(Count); ++i)
707	assert(!(Cache[i] < Cache[i-1]) && "Cache isn't sorted!")((!(Cache[i] < Cache[i-1]) && "Cache isn't sorted!" ) ? static_cast<void> (0) : __assert_fail ("!(Cache[i] < Cache[i-1]) && \"Cache isn't sorted!\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.6~svn224456/lib/Analysis/MemoryDependenceAnalysis.cpp" , 707, __PRETTY_FUNCTION__));
708	}
709	#endif
710
711	/// getNonLocalCallDependency - Perform a full dependency query for the
712	/// specified call, returning the set of blocks that the value is
713	/// potentially live across. The returned set of results will include a
714	/// "NonLocal" result for all blocks where the value is live across.
715	///
716	/// This method assumes the instruction returns a "NonLocal" dependency
717	/// within its own block.
718	///
719	/// This returns a reference to an internal data structure that may be
720	/// invalidated on the next non-local query or when an instruction is
721	/// removed. Clients must copy this data if they want it around longer than
722	/// that.
723	const MemoryDependenceAnalysis::NonLocalDepInfo &
724	MemoryDependenceAnalysis::getNonLocalCallDependency(CallSite QueryCS) {
725	assert(getDependency(QueryCS.getInstruction()).isNonLocal() &&((getDependency(QueryCS.getInstruction()).isNonLocal() && "getNonLocalCallDependency should only be used on calls with non-local deps!" ) ? static_cast<void> (0) : __assert_fail ("getDependency(QueryCS.getInstruction()).isNonLocal() && \"getNonLocalCallDependency should only be used on calls with non-local deps!\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.6~svn224456/lib/Analysis/MemoryDependenceAnalysis.cpp" , 726, __PRETTY_FUNCTION__))
726	"getNonLocalCallDependency should only be used on calls with non-local deps!")((getDependency(QueryCS.getInstruction()).isNonLocal() && "getNonLocalCallDependency should only be used on calls with non-local deps!" ) ? static_cast<void> (0) : __assert_fail ("getDependency(QueryCS.getInstruction()).isNonLocal() && \"getNonLocalCallDependency should only be used on calls with non-local deps!\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.6~svn224456/lib/Analysis/MemoryDependenceAnalysis.cpp" , 726, __PRETTY_FUNCTION__));
727	PerInstNLInfo &CacheP = NonLocalDeps[QueryCS.getInstruction()];
728	NonLocalDepInfo &Cache = CacheP.first;
729
730	/// DirtyBlocks - This is the set of blocks that need to be recomputed. In
731	/// the cached case, this can happen due to instructions being deleted etc. In
732	/// the uncached case, this starts out as the set of predecessors we care
733	/// about.
734	SmallVector<BasicBlock*, 32> DirtyBlocks;
735
736	if (!Cache.empty()) {
737	// Okay, we have a cache entry. If we know it is not dirty, just return it
738	// with no computation.
739	if (!CacheP.second) {
740	++NumCacheNonLocal;
741	return Cache;
742	}
743
744	// If we already have a partially computed set of results, scan them to
745	// determine what is dirty, seeding our initial DirtyBlocks worklist.
746	for (NonLocalDepInfo::iterator I = Cache.begin(), E = Cache.end();
747	I != E; ++I)
748	if (I->getResult().isDirty())
749	DirtyBlocks.push_back(I->getBB());
750
751	// Sort the cache so that we can do fast binary search lookups below.
752	std::sort(Cache.begin(), Cache.end());
753
754	++NumCacheDirtyNonLocal;
755	//cerr << "CACHED CASE: " << DirtyBlocks.size() << " dirty: "
756	// << Cache.size() << " cached: " << *QueryInst;
757	} else {
758	// Seed DirtyBlocks with each of the preds of QueryInst's block.
759	BasicBlock *QueryBB = QueryCS.getInstruction()->getParent();
760	for (BasicBlock *PI = PredCache->GetPreds(QueryBB); PI; ++PI)
761	DirtyBlocks.push_back(*PI);
762	++NumUncacheNonLocal;
763	}
764
765	// isReadonlyCall - If this is a read-only call, we can be more aggressive.
766	bool isReadonlyCall = AA->onlyReadsMemory(QueryCS);
767
768	SmallPtrSet<BasicBlock*, 64> Visited;
769
770	unsigned NumSortedEntries = Cache.size();
771	DEBUG(AssertSorted(Cache))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("memdep")) { AssertSorted(Cache); } } while (0);
772
773	// Iterate while we still have blocks to update.
774	while (!DirtyBlocks.empty()) {
775	BasicBlock *DirtyBB = DirtyBlocks.back();
776	DirtyBlocks.pop_back();
777
778	// Already processed this block?
779	if (!Visited.insert(DirtyBB).second)
780	continue;
781
782	// Do a binary search to see if we already have an entry for this block in
783	// the cache set. If so, find it.
784	DEBUG(AssertSorted(Cache, NumSortedEntries))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("memdep")) { AssertSorted(Cache, NumSortedEntries); } } while (0);
785	NonLocalDepInfo::iterator Entry =
786	std::upper_bound(Cache.begin(), Cache.begin()+NumSortedEntries,
787	NonLocalDepEntry(DirtyBB));
788	if (Entry != Cache.begin() && std::prev(Entry)->getBB() == DirtyBB)
789	--Entry;
790
791	NonLocalDepEntry *ExistingResult = nullptr;
792	if (Entry != Cache.begin()+NumSortedEntries &&
793	Entry->getBB() == DirtyBB) {
794	// If we already have an entry, and if it isn't already dirty, the block
795	// is done.
796	if (!Entry->getResult().isDirty())
797	continue;
798
799	// Otherwise, remember this slot so we can update the value.
800	ExistingResult = &*Entry;
801	}
802
803	// If the dirty entry has a pointer, start scanning from it so we don't have
804	// to rescan the entire block.
805	BasicBlock::iterator ScanPos = DirtyBB->end();
806	if (ExistingResult) {
807	if (Instruction *Inst = ExistingResult->getResult().getInst()) {
808	ScanPos = Inst;
809	// We're removing QueryInst's use of Inst.
810	RemoveFromReverseMap(ReverseNonLocalDeps, Inst,
811	QueryCS.getInstruction());
812	}
813	}
814
815	// Find out if this block has a local dependency for QueryInst.
816	MemDepResult Dep;
817
818	if (ScanPos != DirtyBB->begin()) {
819	Dep = getCallSiteDependencyFrom(QueryCS, isReadonlyCall,ScanPos, DirtyBB);
820	} else if (DirtyBB != &DirtyBB->getParent()->getEntryBlock()) {
821	// No dependence found. If this is the entry block of the function, it is
822	// a clobber, otherwise it is unknown.
823	Dep = MemDepResult::getNonLocal();
824	} else {
825	Dep = MemDepResult::getNonFuncLocal();
826	}
827
828	// If we had a dirty entry for the block, update it. Otherwise, just add
829	// a new entry.
830	if (ExistingResult)
831	ExistingResult->setResult(Dep);
832	else
833	Cache.push_back(NonLocalDepEntry(DirtyBB, Dep));
834
835	// If the block has a dependency (i.e. it isn't completely transparent to
836	// the value), remember the association!
837	if (!Dep.isNonLocal()) {
838	// Keep the ReverseNonLocalDeps map up to date so we can efficiently
839	// update this when we remove instructions.
840	if (Instruction *Inst = Dep.getInst())
841	ReverseNonLocalDeps[Inst].insert(QueryCS.getInstruction());
842	} else {
843
844	// If the block is completely transparent to the load, we need to check
845	// the predecessors of this block. Add them to our worklist.
846	for (BasicBlock *PI = PredCache->GetPreds(DirtyBB); PI; ++PI)
847	DirtyBlocks.push_back(*PI);
848	}
849	}
850
851	return Cache;
852	}
853
854	/// getNonLocalPointerDependency - Perform a full dependency query for an
855	/// access to the specified (non-volatile) memory location, returning the
856	/// set of instructions that either define or clobber the value.
857	///
858	/// This method assumes the pointer has a "NonLocal" dependency within its
859	/// own block.
860	///
861	void MemoryDependenceAnalysis::
862	getNonLocalPointerDependency(const AliasAnalysis::Location &Loc, bool isLoad,
863	BasicBlock *FromBB,
864	SmallVectorImpl<NonLocalDepResult> &Result) {
865	assert(Loc.Ptr->getType()->isPointerTy() &&((Loc.Ptr->getType()->isPointerTy() && "Can't get pointer deps of a non-pointer!" ) ? static_cast<void> (0) : __assert_fail ("Loc.Ptr->getType()->isPointerTy() && \"Can't get pointer deps of a non-pointer!\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.6~svn224456/lib/Analysis/MemoryDependenceAnalysis.cpp" , 866, __PRETTY_FUNCTION__))
866	"Can't get pointer deps of a non-pointer!")((Loc.Ptr->getType()->isPointerTy() && "Can't get pointer deps of a non-pointer!" ) ? static_cast<void> (0) : __assert_fail ("Loc.Ptr->getType()->isPointerTy() && \"Can't get pointer deps of a non-pointer!\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.6~svn224456/lib/Analysis/MemoryDependenceAnalysis.cpp" , 866, __PRETTY_FUNCTION__));
867	Result.clear();
868
869	PHITransAddr Address(const_cast<Value *>(Loc.Ptr), DL, AT);
870
871	// This is the set of blocks we've inspected, and the pointer we consider in
872	// each block. Because of critical edges, we currently bail out if querying
873	// a block with multiple different pointers. This can happen during PHI
874	// translation.
875	DenseMap<BasicBlock, Value> Visited;
876	if (!getNonLocalPointerDepFromBB(Address, Loc, isLoad, FromBB,
877	Result, Visited, true))
878	return;
879	Result.clear();
880	Result.push_back(NonLocalDepResult(FromBB,
881	MemDepResult::getUnknown(),
882	const_cast<Value *>(Loc.Ptr)));
883	}
884
885	/// GetNonLocalInfoForBlock - Compute the memdep value for BB with
886	/// Pointer/PointeeSize using either cached information in Cache or by doing a
887	/// lookup (which may use dirty cache info if available). If we do a lookup,
888	/// add the result to the cache.
889	MemDepResult MemoryDependenceAnalysis::
890	GetNonLocalInfoForBlock(const AliasAnalysis::Location &Loc,
891	bool isLoad, BasicBlock *BB,
892	NonLocalDepInfo *Cache, unsigned NumSortedEntries) {
893
894	// Do a binary search to see if we already have an entry for this block in
895	// the cache set. If so, find it.
896	NonLocalDepInfo::iterator Entry =
897	std::upper_bound(Cache->begin(), Cache->begin()+NumSortedEntries,
898	NonLocalDepEntry(BB));
899	if (Entry != Cache->begin() && (Entry-1)->getBB() == BB)
900	--Entry;
901
902	NonLocalDepEntry *ExistingResult = nullptr;
903	if (Entry != Cache->begin()+NumSortedEntries && Entry->getBB() == BB)
904	ExistingResult = &*Entry;
905
906	// If we have a cached entry, and it is non-dirty, use it as the value for
907	// this dependency.
908	if (ExistingResult && !ExistingResult->getResult().isDirty()) {
909	++NumCacheNonLocalPtr;
910	return ExistingResult->getResult();
911	}
912
913	// Otherwise, we have to scan for the value. If we have a dirty cache
914	// entry, start scanning from its position, otherwise we scan from the end
915	// of the block.
916	BasicBlock::iterator ScanPos = BB->end();
917	if (ExistingResult && ExistingResult->getResult().getInst()) {
918	assert(ExistingResult->getResult().getInst()->getParent() == BB &&((ExistingResult->getResult().getInst()->getParent() == BB && "Instruction invalidated?") ? static_cast<void > (0) : __assert_fail ("ExistingResult->getResult().getInst()->getParent() == BB && \"Instruction invalidated?\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.6~svn224456/lib/Analysis/MemoryDependenceAnalysis.cpp" , 919, __PRETTY_FUNCTION__))
919	"Instruction invalidated?")((ExistingResult->getResult().getInst()->getParent() == BB && "Instruction invalidated?") ? static_cast<void > (0) : __assert_fail ("ExistingResult->getResult().getInst()->getParent() == BB && \"Instruction invalidated?\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.6~svn224456/lib/Analysis/MemoryDependenceAnalysis.cpp" , 919, __PRETTY_FUNCTION__));
920	++NumCacheDirtyNonLocalPtr;
921	ScanPos = ExistingResult->getResult().getInst();
922
923	// Eliminating the dirty entry from 'Cache', so update the reverse info.
924	ValueIsLoadPair CacheKey(Loc.Ptr, isLoad);
925	RemoveFromReverseMap(ReverseNonLocalPtrDeps, ScanPos, CacheKey);
926	} else {
927	++NumUncacheNonLocalPtr;
928	}
929
930	// Scan the block for the dependency.
931	MemDepResult Dep = getPointerDependencyFrom(Loc, isLoad, ScanPos, BB);
932
933	// If we had a dirty entry for the block, update it. Otherwise, just add
934	// a new entry.
935	if (ExistingResult)
936	ExistingResult->setResult(Dep);
937	else
938	Cache->push_back(NonLocalDepEntry(BB, Dep));
939
940	// If the block has a dependency (i.e. it isn't completely transparent to
941	// the value), remember the reverse association because we just added it
942	// to Cache!
943	if (!Dep.isDef() && !Dep.isClobber())
944	return Dep;
945
946	// Keep the ReverseNonLocalPtrDeps map up to date so we can efficiently
947	// update MemDep when we remove instructions.
948	Instruction *Inst = Dep.getInst();
949	assert(Inst && "Didn't depend on anything?")((Inst && "Didn't depend on anything?") ? static_cast <void> (0) : __assert_fail ("Inst && \"Didn't depend on anything?\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.6~svn224456/lib/Analysis/MemoryDependenceAnalysis.cpp" , 949, __PRETTY_FUNCTION__));
950	ValueIsLoadPair CacheKey(Loc.Ptr, isLoad);
951	ReverseNonLocalPtrDeps[Inst].insert(CacheKey);
952	return Dep;
953	}
954
955	/// SortNonLocalDepInfoCache - Sort the NonLocalDepInfo cache, given a certain
956	/// number of elements in the array that are already properly ordered. This is
957	/// optimized for the case when only a few entries are added.
958	static void
959	SortNonLocalDepInfoCache(MemoryDependenceAnalysis::NonLocalDepInfo &Cache,
960	unsigned NumSortedEntries) {
961	switch (Cache.size() - NumSortedEntries) {
962	case 0:
963	// done, no new entries.
964	break;
965	case 2: {
966	// Two new entries, insert the last one into place.
967	NonLocalDepEntry Val = Cache.back();
968	Cache.pop_back();
969	MemoryDependenceAnalysis::NonLocalDepInfo::iterator Entry =
970	std::upper_bound(Cache.begin(), Cache.end()-1, Val);
971	Cache.insert(Entry, Val);
972	// FALL THROUGH.
973	}
974	case 1:
975	// One new entry, Just insert the new value at the appropriate position.
976	if (Cache.size() != 1) {
977	NonLocalDepEntry Val = Cache.back();
978	Cache.pop_back();
979	MemoryDependenceAnalysis::NonLocalDepInfo::iterator Entry =
980	std::upper_bound(Cache.begin(), Cache.end(), Val);
981	Cache.insert(Entry, Val);
982	}
983	break;
984	default:
985	// Added many values, do a full scale sort.
986	std::sort(Cache.begin(), Cache.end());
987	break;
988	}
989	}
990
991	/// getNonLocalPointerDepFromBB - Perform a dependency query based on
992	/// pointer/pointeesize starting at the end of StartBB. Add any clobber/def
993	/// results to the results vector and keep track of which blocks are visited in
994	/// 'Visited'.
995	///
996	/// This has special behavior for the first block queries (when SkipFirstBlock
997	/// is true). In this special case, it ignores the contents of the specified
998	/// block and starts returning dependence info for its predecessors.
999	///
1000	/// This function returns false on success, or true to indicate that it could
1001	/// not compute dependence information for some reason. This should be treated
1002	/// as a clobber dependence on the first instruction in the predecessor block.
1003	bool MemoryDependenceAnalysis::
1004	getNonLocalPointerDepFromBB(const PHITransAddr &Pointer,
1005	const AliasAnalysis::Location &Loc,
1006	bool isLoad, BasicBlock *StartBB,
1007	SmallVectorImpl<NonLocalDepResult> &Result,
1008	DenseMap<BasicBlock, Value> &Visited,
1009	bool SkipFirstBlock) {
1010	// Look up the cached info for Pointer.
1011	ValueIsLoadPair CacheKey(Pointer.getAddr(), isLoad);
1012
1013	// Set up a temporary NLPI value. If the map doesn't yet have an entry for
1014	// CacheKey, this value will be inserted as the associated value. Otherwise,
1015	// it'll be ignored, and we'll have to check to see if the cached size and
1016	// aa tags are consistent with the current query.
1017	NonLocalPointerInfo InitialNLPI;
1018	InitialNLPI.Size = Loc.Size;
1019	InitialNLPI.AATags = Loc.AATags;
1020
1021	// Get the NLPI for CacheKey, inserting one into the map if it doesn't
1022	// already have one.
1023	std::pair<CachedNonLocalPointerInfo::iterator, bool> Pair =
1024	NonLocalPointerDeps.insert(std::make_pair(CacheKey, InitialNLPI));
1025	NonLocalPointerInfo *CacheInfo = &Pair.first->second;
1026
1027	// If we already have a cache entry for this CacheKey, we may need to do some
1028	// work to reconcile the cache entry and the current query.
1029	if (!Pair.second) {
1030	if (CacheInfo->Size < Loc.Size) {
1031	// The query's Size is greater than the cached one. Throw out the
1032	// cached data and proceed with the query at the greater size.
1033	CacheInfo->Pair = BBSkipFirstBlockPair();
1034	CacheInfo->Size = Loc.Size;
1035	for (NonLocalDepInfo::iterator DI = CacheInfo->NonLocalDeps.begin(),
1036	DE = CacheInfo->NonLocalDeps.end(); DI != DE; ++DI)
1037	if (Instruction *Inst = DI->getResult().getInst())
1038	RemoveFromReverseMap(ReverseNonLocalPtrDeps, Inst, CacheKey);
1039	CacheInfo->NonLocalDeps.clear();
1040	} else if (CacheInfo->Size > Loc.Size) {
1041	// This query's Size is less than the cached one. Conservatively restart
1042	// the query using the greater size.
1043	return getNonLocalPointerDepFromBB(Pointer,
1044	Loc.getWithNewSize(CacheInfo->Size),
1045	isLoad, StartBB, Result, Visited,
1046	SkipFirstBlock);
1047	}
1048
1049	// If the query's AATags are inconsistent with the cached one,
1050	// conservatively throw out the cached data and restart the query with
1051	// no tag if needed.
1052	if (CacheInfo->AATags != Loc.AATags) {
1053	if (CacheInfo->AATags) {
1054	CacheInfo->Pair = BBSkipFirstBlockPair();
1055	CacheInfo->AATags = AAMDNodes();
1056	for (NonLocalDepInfo::iterator DI = CacheInfo->NonLocalDeps.begin(),
1057	DE = CacheInfo->NonLocalDeps.end(); DI != DE; ++DI)
1058	if (Instruction *Inst = DI->getResult().getInst())
1059	RemoveFromReverseMap(ReverseNonLocalPtrDeps, Inst, CacheKey);
1060	CacheInfo->NonLocalDeps.clear();
1061	}
1062	if (Loc.AATags)
1063	return getNonLocalPointerDepFromBB(Pointer, Loc.getWithoutAATags(),
1064	isLoad, StartBB, Result, Visited,
1065	SkipFirstBlock);
1066	}
1067	}
1068
1069	NonLocalDepInfo *Cache = &CacheInfo->NonLocalDeps;
1070
1071	// If we have valid cached information for exactly the block we are
1072	// investigating, just return it with no recomputation.
1073	if (CacheInfo->Pair == BBSkipFirstBlockPair(StartBB, SkipFirstBlock)) {
1074	// We have a fully cached result for this query then we can just return the
1075	// cached results and populate the visited set. However, we have to verify
1076	// that we don't already have conflicting results for these blocks. Check
1077	// to ensure that if a block in the results set is in the visited set that
1078	// it was for the same pointer query.
1079	if (!Visited.empty()) {
1080	for (NonLocalDepInfo::iterator I = Cache->begin(), E = Cache->end();
1081	I != E; ++I) {
1082	DenseMap<BasicBlock, Value>::iterator VI = Visited.find(I->getBB());
1083	if (VI == Visited.end() \|\| VI->second == Pointer.getAddr())
1084	continue;
1085
1086	// We have a pointer mismatch in a block. Just return clobber, saying
1087	// that something was clobbered in this result. We could also do a
1088	// non-fully cached query, but there is little point in doing this.
1089	return true;
1090	}
1091	}
1092
1093	Value *Addr = Pointer.getAddr();
1094	for (NonLocalDepInfo::iterator I = Cache->begin(), E = Cache->end();
1095	I != E; ++I) {
1096	Visited.insert(std::make_pair(I->getBB(), Addr));
1097	if (I->getResult().isNonLocal()) {
1098	continue;
1099	}
1100
1101	if (!DT) {
1102	Result.push_back(NonLocalDepResult(I->getBB(),
1103	MemDepResult::getUnknown(),
1104	Addr));
1105	} else if (DT->isReachableFromEntry(I->getBB())) {
1106	Result.push_back(NonLocalDepResult(I->getBB(), I->getResult(), Addr));
1107	}
1108	}
1109	++NumCacheCompleteNonLocalPtr;
1110	return false;
1111	}
1112
1113	// Otherwise, either this is a new block, a block with an invalid cache
1114	// pointer or one that we're about to invalidate by putting more info into it
1115	// than its valid cache info. If empty, the result will be valid cache info,
1116	// otherwise it isn't.
1117	if (Cache->empty())
1118	CacheInfo->Pair = BBSkipFirstBlockPair(StartBB, SkipFirstBlock);
1119	else
1120	CacheInfo->Pair = BBSkipFirstBlockPair();
1121
1122	SmallVector<BasicBlock*, 32> Worklist;
1123	Worklist.push_back(StartBB);
1124
1125	// PredList used inside loop.
1126	SmallVector<std::pair<BasicBlock*, PHITransAddr>, 16> PredList;
1127
1128	// Keep track of the entries that we know are sorted. Previously cached
1129	// entries will all be sorted. The entries we add we only sort on demand (we
1130	// don't insert every element into its sorted position). We know that we
1131	// won't get any reuse from currently inserted values, because we don't
1132	// revisit blocks after we insert info for them.
1133	unsigned NumSortedEntries = Cache->size();
1134	DEBUG(AssertSorted(Cache))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("memdep")) { AssertSorted(Cache); } } while (0);
1135
1136	while (!Worklist.empty()) {
1137	BasicBlock *BB = Worklist.pop_back_val();
1138
1139	// If we do process a large number of blocks it becomes very expensive and
1140	// likely it isn't worth worrying about
1141	if (Result.size() > NumResultsLimit) {
1142	Worklist.clear();
1143	// Sort it now (if needed) so that recursive invocations of
1144	// getNonLocalPointerDepFromBB and other routines that could reuse the
1145	// cache value will only see properly sorted cache arrays.
1146	if (Cache && NumSortedEntries != Cache->size()) {
1147	SortNonLocalDepInfoCache(*Cache, NumSortedEntries);
1148	NumSortedEntries = Cache->size();
	Value stored to 'NumSortedEntries' is never read
1149	}
1150	// Since we bail out, the "Cache" set won't contain all of the
1151	// results for the query. This is ok (we can still use it to accelerate
1152	// specific block queries) but we can't do the fastpath "return all
1153	// results from the set". Clear out the indicator for this.
1154	CacheInfo->Pair = BBSkipFirstBlockPair();
1155	return true;
1156	}
1157
1158	// Skip the first block if we have it.
1159	if (!SkipFirstBlock) {
1160	// Analyze the dependency of *Pointer in FromBB. See if we already have
1161	// been here.
1162	assert(Visited.count(BB) && "Should check 'visited' before adding to WL")((Visited.count(BB) && "Should check 'visited' before adding to WL" ) ? static_cast<void> (0) : __assert_fail ("Visited.count(BB) && \"Should check 'visited' before adding to WL\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.6~svn224456/lib/Analysis/MemoryDependenceAnalysis.cpp" , 1162, __PRETTY_FUNCTION__));
1163
1164	// Get the dependency info for Pointer in BB. If we have cached
1165	// information, we will use it, otherwise we compute it.
1166	DEBUG(AssertSorted(Cache, NumSortedEntries))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("memdep")) { AssertSorted(Cache, NumSortedEntries); } } while (0);
1167	MemDepResult Dep = GetNonLocalInfoForBlock(Loc, isLoad, BB, Cache,
1168	NumSortedEntries);
1169
1170	// If we got a Def or Clobber, add this to the list of results.
1171	if (!Dep.isNonLocal()) {
1172	if (!DT) {
1173	Result.push_back(NonLocalDepResult(BB,
1174	MemDepResult::getUnknown(),
1175	Pointer.getAddr()));
1176	continue;
1177	} else if (DT->isReachableFromEntry(BB)) {
1178	Result.push_back(NonLocalDepResult(BB, Dep, Pointer.getAddr()));
1179	continue;
1180	}
1181	}
1182	}
1183
1184	// If 'Pointer' is an instruction defined in this block, then we need to do
1185	// phi translation to change it into a value live in the predecessor block.
1186	// If not, we just add the predecessors to the worklist and scan them with
1187	// the same Pointer.
1188	if (!Pointer.NeedsPHITranslationFromBlock(BB)) {
1189	SkipFirstBlock = false;
1190	SmallVector<BasicBlock*, 16> NewBlocks;
1191	for (BasicBlock *PI = PredCache->GetPreds(BB); PI; ++PI) {
1192	// Verify that we haven't looked at this block yet.
1193	std::pair<DenseMap<BasicBlock,Value>::iterator, bool>
1194	InsertRes = Visited.insert(std::make_pair(*PI, Pointer.getAddr()));
1195	if (InsertRes.second) {
1196	// First time we've looked at *PI.
1197	NewBlocks.push_back(*PI);
1198	continue;
1199	}
1200
1201	// If we have seen this block before, but it was with a different
1202	// pointer then we have a phi translation failure and we have to treat
1203	// this as a clobber.
1204	if (InsertRes.first->second != Pointer.getAddr()) {
1205	// Make sure to clean up the Visited map before continuing on to
1206	// PredTranslationFailure.
1207	for (unsigned i = 0; i < NewBlocks.size(); i++)
1208	Visited.erase(NewBlocks[i]);
1209	goto PredTranslationFailure;
1210	}
1211	}
1212	Worklist.append(NewBlocks.begin(), NewBlocks.end());
1213	continue;
1214	}
1215
1216	// We do need to do phi translation, if we know ahead of time we can't phi
1217	// translate this value, don't even try.
1218	if (!Pointer.IsPotentiallyPHITranslatable())
1219	goto PredTranslationFailure;
1220
1221	// We may have added values to the cache list before this PHI translation.
1222	// If so, we haven't done anything to ensure that the cache remains sorted.
1223	// Sort it now (if needed) so that recursive invocations of
1224	// getNonLocalPointerDepFromBB and other routines that could reuse the cache
1225	// value will only see properly sorted cache arrays.
1226	if (Cache && NumSortedEntries != Cache->size()) {
1227	SortNonLocalDepInfoCache(*Cache, NumSortedEntries);
1228	NumSortedEntries = Cache->size();
1229	}
1230	Cache = nullptr;
1231
1232	PredList.clear();
1233	for (BasicBlock *PI = PredCache->GetPreds(BB); PI; ++PI) {
1234	BasicBlock Pred = PI;
1235	PredList.push_back(std::make_pair(Pred, Pointer));
1236
1237	// Get the PHI translated pointer in this predecessor. This can fail if
1238	// not translatable, in which case the getAddr() returns null.
1239	PHITransAddr &PredPointer = PredList.back().second;
1240	PredPointer.PHITranslateValue(BB, Pred, nullptr);
1241
1242	Value *PredPtrVal = PredPointer.getAddr();
1243
1244	// Check to see if we have already visited this pred block with another
1245	// pointer. If so, we can't do this lookup. This failure can occur
1246	// with PHI translation when a critical edge exists and the PHI node in
1247	// the successor translates to a pointer value different than the
1248	// pointer the block was first analyzed with.
1249	std::pair<DenseMap<BasicBlock,Value>::iterator, bool>
1250	InsertRes = Visited.insert(std::make_pair(Pred, PredPtrVal));
1251
1252	if (!InsertRes.second) {
1253	// We found the pred; take it off the list of preds to visit.
1254	PredList.pop_back();
1255
1256	// If the predecessor was visited with PredPtr, then we already did
1257	// the analysis and can ignore it.
1258	if (InsertRes.first->second == PredPtrVal)
1259	continue;
1260
1261	// Otherwise, the block was previously analyzed with a different
1262	// pointer. We can't represent the result of this case, so we just
1263	// treat this as a phi translation failure.
1264
1265	// Make sure to clean up the Visited map before continuing on to
1266	// PredTranslationFailure.
1267	for (unsigned i = 0, n = PredList.size(); i < n; ++i)
1268	Visited.erase(PredList[i].first);
1269
1270	goto PredTranslationFailure;
1271	}
1272	}
1273
1274	// Actually process results here; this need to be a separate loop to avoid
1275	// calling getNonLocalPointerDepFromBB for blocks we don't want to return
1276	// any results for. (getNonLocalPointerDepFromBB will modify our
1277	// datastructures in ways the code after the PredTranslationFailure label
1278	// doesn't expect.)
1279	for (unsigned i = 0, n = PredList.size(); i < n; ++i) {
1280	BasicBlock *Pred = PredList[i].first;
1281	PHITransAddr &PredPointer = PredList[i].second;
1282	Value *PredPtrVal = PredPointer.getAddr();
1283
1284	bool CanTranslate = true;
1285	// If PHI translation was unable to find an available pointer in this
1286	// predecessor, then we have to assume that the pointer is clobbered in
1287	// that predecessor. We can still do PRE of the load, which would insert
1288	// a computation of the pointer in this predecessor.
1289	if (!PredPtrVal)
1290	CanTranslate = false;
1291
1292	// FIXME: it is entirely possible that PHI translating will end up with
1293	// the same value. Consider PHI translating something like:
1294	// X = phi [x, bb1], [y, bb2]. PHI translating for bb1 doesn't need
1295	// to recurse here, pedantically speaking.
1296
1297	// If getNonLocalPointerDepFromBB fails here, that means the cached
1298	// result conflicted with the Visited list; we have to conservatively
1299	// assume it is unknown, but this also does not block PRE of the load.
1300	if (!CanTranslate \|\|
1301	getNonLocalPointerDepFromBB(PredPointer,
1302	Loc.getWithNewPtr(PredPtrVal),
1303	isLoad, Pred,
1304	Result, Visited)) {
1305	// Add the entry to the Result list.
1306	NonLocalDepResult Entry(Pred, MemDepResult::getUnknown(), PredPtrVal);
1307	Result.push_back(Entry);
1308
1309	// Since we had a phi translation failure, the cache for CacheKey won't
1310	// include all of the entries that we need to immediately satisfy future
1311	// queries. Mark this in NonLocalPointerDeps by setting the
1312	// BBSkipFirstBlockPair pointer to null. This requires reuse of the
1313	// cached value to do more work but not miss the phi trans failure.
1314	NonLocalPointerInfo &NLPI = NonLocalPointerDeps[CacheKey];
1315	NLPI.Pair = BBSkipFirstBlockPair();
1316	continue;
1317	}
1318	}
1319
1320	// Refresh the CacheInfo/Cache pointer so that it isn't invalidated.
1321	CacheInfo = &NonLocalPointerDeps[CacheKey];
1322	Cache = &CacheInfo->NonLocalDeps;
1323	NumSortedEntries = Cache->size();
1324
1325	// Since we did phi translation, the "Cache" set won't contain all of the
1326	// results for the query. This is ok (we can still use it to accelerate
1327	// specific block queries) but we can't do the fastpath "return all
1328	// results from the set" Clear out the indicator for this.
1329	CacheInfo->Pair = BBSkipFirstBlockPair();
1330	SkipFirstBlock = false;
1331	continue;
1332
1333	PredTranslationFailure:
1334	// The following code is "failure"; we can't produce a sane translation
1335	// for the given block. It assumes that we haven't modified any of
1336	// our datastructures while processing the current block.
1337
1338	if (!Cache) {
1339	// Refresh the CacheInfo/Cache pointer if it got invalidated.
1340	CacheInfo = &NonLocalPointerDeps[CacheKey];
1341	Cache = &CacheInfo->NonLocalDeps;
1342	NumSortedEntries = Cache->size();
1343	}
1344
1345	// Since we failed phi translation, the "Cache" set won't contain all of the
1346	// results for the query. This is ok (we can still use it to accelerate
1347	// specific block queries) but we can't do the fastpath "return all
1348	// results from the set". Clear out the indicator for this.
1349	CacheInfo->Pair = BBSkipFirstBlockPair();
1350
1351	// If nothing works, mark the pointer as unknown.
1352	//
1353	// If this is the magic first block, return this as a clobber of the whole
1354	// incoming value. Since we can't phi translate to one of the predecessors,
1355	// we have to bail out.
1356	if (SkipFirstBlock)
1357	return true;
1358
1359	for (NonLocalDepInfo::reverse_iterator I = Cache->rbegin(); ; ++I) {
1360	assert(I != Cache->rend() && "Didn't find current block??")((I != Cache->rend() && "Didn't find current block??" ) ? static_cast<void> (0) : __assert_fail ("I != Cache->rend() && \"Didn't find current block??\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.6~svn224456/lib/Analysis/MemoryDependenceAnalysis.cpp" , 1360, __PRETTY_FUNCTION__));
1361	if (I->getBB() != BB)
1362	continue;
1363
1364	assert((I->getResult().isNonLocal() \|\| !DT->isReachableFromEntry(BB)) &&(((I->getResult().isNonLocal() \|\| !DT->isReachableFromEntry (BB)) && "Should only be here with transparent block" ) ? static_cast<void> (0) : __assert_fail ("(I->getResult().isNonLocal() \|\| !DT->isReachableFromEntry(BB)) && \"Should only be here with transparent block\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.6~svn224456/lib/Analysis/MemoryDependenceAnalysis.cpp" , 1365, __PRETTY_FUNCTION__))
1365	"Should only be here with transparent block")(((I->getResult().isNonLocal() \|\| !DT->isReachableFromEntry (BB)) && "Should only be here with transparent block" ) ? static_cast<void> (0) : __assert_fail ("(I->getResult().isNonLocal() \|\| !DT->isReachableFromEntry(BB)) && \"Should only be here with transparent block\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.6~svn224456/lib/Analysis/MemoryDependenceAnalysis.cpp" , 1365, __PRETTY_FUNCTION__));
1366	I->setResult(MemDepResult::getUnknown());
1367	Result.push_back(NonLocalDepResult(I->getBB(), I->getResult(),
1368	Pointer.getAddr()));
1369	break;
1370	}
1371	}
1372
1373	// Okay, we're done now. If we added new values to the cache, re-sort it.
1374	SortNonLocalDepInfoCache(*Cache, NumSortedEntries);
1375	DEBUG(AssertSorted(Cache))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("memdep")) { AssertSorted(Cache); } } while (0);
1376	return false;
1377	}
1378
1379	/// RemoveCachedNonLocalPointerDependencies - If P exists in
1380	/// CachedNonLocalPointerInfo, remove it.
1381	void MemoryDependenceAnalysis::
1382	RemoveCachedNonLocalPointerDependencies(ValueIsLoadPair P) {
1383	CachedNonLocalPointerInfo::iterator It =
1384	NonLocalPointerDeps.find(P);
1385	if (It == NonLocalPointerDeps.end()) return;
1386
1387	// Remove all of the entries in the BB->val map. This involves removing
1388	// instructions from the reverse map.
1389	NonLocalDepInfo &PInfo = It->second.NonLocalDeps;
1390
1391	for (unsigned i = 0, e = PInfo.size(); i != e; ++i) {
1392	Instruction *Target = PInfo[i].getResult().getInst();
1393	if (!Target) continue; // Ignore non-local dep results.
1394	assert(Target->getParent() == PInfo[i].getBB())((Target->getParent() == PInfo[i].getBB()) ? static_cast< void> (0) : __assert_fail ("Target->getParent() == PInfo[i].getBB()" , "/tmp/buildd/llvm-toolchain-snapshot-3.6~svn224456/lib/Analysis/MemoryDependenceAnalysis.cpp" , 1394, __PRETTY_FUNCTION__));
1395
1396	// Eliminating the dirty entry from 'Cache', so update the reverse info.
1397	RemoveFromReverseMap(ReverseNonLocalPtrDeps, Target, P);
1398	}
1399
1400	// Remove P from NonLocalPointerDeps (which deletes NonLocalDepInfo).
1401	NonLocalPointerDeps.erase(It);
1402	}
1403
1404
1405	/// invalidateCachedPointerInfo - This method is used to invalidate cached
1406	/// information about the specified pointer, because it may be too
1407	/// conservative in memdep. This is an optional call that can be used when
1408	/// the client detects an equivalence between the pointer and some other
1409	/// value and replaces the other value with ptr. This can make Ptr available
1410	/// in more places that cached info does not necessarily keep.
1411	void MemoryDependenceAnalysis::invalidateCachedPointerInfo(Value *Ptr) {
1412	// If Ptr isn't really a pointer, just ignore it.
1413	if (!Ptr->getType()->isPointerTy()) return;
1414	// Flush store info for the pointer.
1415	RemoveCachedNonLocalPointerDependencies(ValueIsLoadPair(Ptr, false));
1416	// Flush load info for the pointer.
1417	RemoveCachedNonLocalPointerDependencies(ValueIsLoadPair(Ptr, true));
1418	}
1419
1420	/// invalidateCachedPredecessors - Clear the PredIteratorCache info.
1421	/// This needs to be done when the CFG changes, e.g., due to splitting
1422	/// critical edges.
1423	void MemoryDependenceAnalysis::invalidateCachedPredecessors() {
1424	PredCache->clear();
1425	}
1426
1427	/// removeInstruction - Remove an instruction from the dependence analysis,
1428	/// updating the dependence of instructions that previously depended on it.
1429	/// This method attempts to keep the cache coherent using the reverse map.
1430	void MemoryDependenceAnalysis::removeInstruction(Instruction *RemInst) {
1431	// Walk through the Non-local dependencies, removing this one as the value
1432	// for any cached queries.
1433	NonLocalDepMapType::iterator NLDI = NonLocalDeps.find(RemInst);
1434	if (NLDI != NonLocalDeps.end()) {
1435	NonLocalDepInfo &BlockMap = NLDI->second.first;
1436	for (NonLocalDepInfo::iterator DI = BlockMap.begin(), DE = BlockMap.end();
1437	DI != DE; ++DI)
1438	if (Instruction *Inst = DI->getResult().getInst())
1439	RemoveFromReverseMap(ReverseNonLocalDeps, Inst, RemInst);
1440	NonLocalDeps.erase(NLDI);
1441	}
1442
1443	// If we have a cached local dependence query for this instruction, remove it.
1444	//
1445	LocalDepMapType::iterator LocalDepEntry = LocalDeps.find(RemInst);
1446	if (LocalDepEntry != LocalDeps.end()) {
1447	// Remove us from DepInst's reverse set now that the local dep info is gone.
1448	if (Instruction *Inst = LocalDepEntry->second.getInst())
1449	RemoveFromReverseMap(ReverseLocalDeps, Inst, RemInst);
1450
1451	// Remove this local dependency info.
1452	LocalDeps.erase(LocalDepEntry);
1453	}
1454
1455	// If we have any cached pointer dependencies on this instruction, remove
1456	// them. If the instruction has non-pointer type, then it can't be a pointer
1457	// base.
1458
1459	// Remove it from both the load info and the store info. The instruction
1460	// can't be in either of these maps if it is non-pointer.
1461	if (RemInst->getType()->isPointerTy()) {
1462	RemoveCachedNonLocalPointerDependencies(ValueIsLoadPair(RemInst, false));
1463	RemoveCachedNonLocalPointerDependencies(ValueIsLoadPair(RemInst, true));
1464	}
1465
1466	// Loop over all of the things that depend on the instruction we're removing.
1467	//
1468	SmallVector<std::pair<Instruction, Instruction>, 8> ReverseDepsToAdd;
1469
1470	// If we find RemInst as a clobber or Def in any of the maps for other values,
1471	// we need to replace its entry with a dirty version of the instruction after
1472	// it. If RemInst is a terminator, we use a null dirty value.
1473	//
1474	// Using a dirty version of the instruction after RemInst saves having to scan
1475	// the entire block to get to this point.
1476	MemDepResult NewDirtyVal;
1477	if (!RemInst->isTerminator())
1478	NewDirtyVal = MemDepResult::getDirty(++BasicBlock::iterator(RemInst));
1479
1480	ReverseDepMapType::iterator ReverseDepIt = ReverseLocalDeps.find(RemInst);
1481	if (ReverseDepIt != ReverseLocalDeps.end()) {
1482	// RemInst can't be the terminator if it has local stuff depending on it.
1483	assert(!ReverseDepIt->second.empty() && !isa<TerminatorInst>(RemInst) &&((!ReverseDepIt->second.empty() && !isa<TerminatorInst >(RemInst) && "Nothing can locally depend on a terminator" ) ? static_cast<void> (0) : __assert_fail ("!ReverseDepIt->second.empty() && !isa<TerminatorInst>(RemInst) && \"Nothing can locally depend on a terminator\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.6~svn224456/lib/Analysis/MemoryDependenceAnalysis.cpp" , 1484, __PRETTY_FUNCTION__))
1484	"Nothing can locally depend on a terminator")((!ReverseDepIt->second.empty() && !isa<TerminatorInst >(RemInst) && "Nothing can locally depend on a terminator" ) ? static_cast<void> (0) : __assert_fail ("!ReverseDepIt->second.empty() && !isa<TerminatorInst>(RemInst) && \"Nothing can locally depend on a terminator\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.6~svn224456/lib/Analysis/MemoryDependenceAnalysis.cpp" , 1484, __PRETTY_FUNCTION__));
1485
1486	for (Instruction *InstDependingOnRemInst : ReverseDepIt->second) {
1487	assert(InstDependingOnRemInst != RemInst &&((InstDependingOnRemInst != RemInst && "Already removed our local dep info" ) ? static_cast<void> (0) : __assert_fail ("InstDependingOnRemInst != RemInst && \"Already removed our local dep info\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.6~svn224456/lib/Analysis/MemoryDependenceAnalysis.cpp" , 1488, __PRETTY_FUNCTION__))
1488	"Already removed our local dep info")((InstDependingOnRemInst != RemInst && "Already removed our local dep info" ) ? static_cast<void> (0) : __assert_fail ("InstDependingOnRemInst != RemInst && \"Already removed our local dep info\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.6~svn224456/lib/Analysis/MemoryDependenceAnalysis.cpp" , 1488, __PRETTY_FUNCTION__));
1489
1490	LocalDeps[InstDependingOnRemInst] = NewDirtyVal;
1491
1492	// Make sure to remember that new things depend on NewDepInst.
1493	assert(NewDirtyVal.getInst() && "There is no way something else can have "((NewDirtyVal.getInst() && "There is no way something else can have " "a local dep on this if it is a terminator!") ? static_cast< void> (0) : __assert_fail ("NewDirtyVal.getInst() && \"There is no way something else can have \" \"a local dep on this if it is a terminator!\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.6~svn224456/lib/Analysis/MemoryDependenceAnalysis.cpp" , 1494, __PRETTY_FUNCTION__))
1494	"a local dep on this if it is a terminator!")((NewDirtyVal.getInst() && "There is no way something else can have " "a local dep on this if it is a terminator!") ? static_cast< void> (0) : __assert_fail ("NewDirtyVal.getInst() && \"There is no way something else can have \" \"a local dep on this if it is a terminator!\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.6~svn224456/lib/Analysis/MemoryDependenceAnalysis.cpp" , 1494, __PRETTY_FUNCTION__));
1495	ReverseDepsToAdd.push_back(std::make_pair(NewDirtyVal.getInst(),
1496	InstDependingOnRemInst));
1497	}
1498
1499	ReverseLocalDeps.erase(ReverseDepIt);
1500
1501	// Add new reverse deps after scanning the set, to avoid invalidating the
1502	// 'ReverseDeps' reference.
1503	while (!ReverseDepsToAdd.empty()) {
1504	ReverseLocalDeps[ReverseDepsToAdd.back().first]
1505	.insert(ReverseDepsToAdd.back().second);
1506	ReverseDepsToAdd.pop_back();
1507	}
1508	}
1509
1510	ReverseDepIt = ReverseNonLocalDeps.find(RemInst);
1511	if (ReverseDepIt != ReverseNonLocalDeps.end()) {
1512	for (Instruction *I : ReverseDepIt->second) {
1513	assert(I != RemInst && "Already removed NonLocalDep info for RemInst")((I != RemInst && "Already removed NonLocalDep info for RemInst" ) ? static_cast<void> (0) : __assert_fail ("I != RemInst && \"Already removed NonLocalDep info for RemInst\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.6~svn224456/lib/Analysis/MemoryDependenceAnalysis.cpp" , 1513, __PRETTY_FUNCTION__));
1514
1515	PerInstNLInfo &INLD = NonLocalDeps[I];
1516	// The information is now dirty!
1517	INLD.second = true;
1518
1519	for (NonLocalDepInfo::iterator DI = INLD.first.begin(),
1520	DE = INLD.first.end(); DI != DE; ++DI) {
1521	if (DI->getResult().getInst() != RemInst) continue;
1522
1523	// Convert to a dirty entry for the subsequent instruction.
1524	DI->setResult(NewDirtyVal);
1525
1526	if (Instruction *NextI = NewDirtyVal.getInst())
1527	ReverseDepsToAdd.push_back(std::make_pair(NextI, I));
1528	}
1529	}
1530
1531	ReverseNonLocalDeps.erase(ReverseDepIt);
1532
1533	// Add new reverse deps after scanning the set, to avoid invalidating 'Set'
1534	while (!ReverseDepsToAdd.empty()) {
1535	ReverseNonLocalDeps[ReverseDepsToAdd.back().first]
1536	.insert(ReverseDepsToAdd.back().second);
1537	ReverseDepsToAdd.pop_back();
1538	}
1539	}
1540
1541	// If the instruction is in ReverseNonLocalPtrDeps then it appears as a
1542	// value in the NonLocalPointerDeps info.
1543	ReverseNonLocalPtrDepTy::iterator ReversePtrDepIt =
1544	ReverseNonLocalPtrDeps.find(RemInst);
1545	if (ReversePtrDepIt != ReverseNonLocalPtrDeps.end()) {
1546	SmallVector<std::pair<Instruction*, ValueIsLoadPair>,8> ReversePtrDepsToAdd;
1547
1548	for (ValueIsLoadPair P : ReversePtrDepIt->second) {
1549	assert(P.getPointer() != RemInst &&((P.getPointer() != RemInst && "Already removed NonLocalPointerDeps info for RemInst" ) ? static_cast<void> (0) : __assert_fail ("P.getPointer() != RemInst && \"Already removed NonLocalPointerDeps info for RemInst\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.6~svn224456/lib/Analysis/MemoryDependenceAnalysis.cpp" , 1550, __PRETTY_FUNCTION__))
1550	"Already removed NonLocalPointerDeps info for RemInst")((P.getPointer() != RemInst && "Already removed NonLocalPointerDeps info for RemInst" ) ? static_cast<void> (0) : __assert_fail ("P.getPointer() != RemInst && \"Already removed NonLocalPointerDeps info for RemInst\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.6~svn224456/lib/Analysis/MemoryDependenceAnalysis.cpp" , 1550, __PRETTY_FUNCTION__));
1551
1552	NonLocalDepInfo &NLPDI = NonLocalPointerDeps[P].NonLocalDeps;
1553
1554	// The cache is not valid for any specific block anymore.
1555	NonLocalPointerDeps[P].Pair = BBSkipFirstBlockPair();
1556
1557	// Update any entries for RemInst to use the instruction after it.
1558	for (NonLocalDepInfo::iterator DI = NLPDI.begin(), DE = NLPDI.end();
1559	DI != DE; ++DI) {
1560	if (DI->getResult().getInst() != RemInst) continue;
1561
1562	// Convert to a dirty entry for the subsequent instruction.
1563	DI->setResult(NewDirtyVal);
1564
1565	if (Instruction *NewDirtyInst = NewDirtyVal.getInst())
1566	ReversePtrDepsToAdd.push_back(std::make_pair(NewDirtyInst, P));
1567	}
1568
1569	// Re-sort the NonLocalDepInfo. Changing the dirty entry to its
1570	// subsequent value may invalidate the sortedness.
1571	std::sort(NLPDI.begin(), NLPDI.end());
1572	}
1573
1574	ReverseNonLocalPtrDeps.erase(ReversePtrDepIt);
1575
1576	while (!ReversePtrDepsToAdd.empty()) {
1577	ReverseNonLocalPtrDeps[ReversePtrDepsToAdd.back().first]
1578	.insert(ReversePtrDepsToAdd.back().second);
1579	ReversePtrDepsToAdd.pop_back();
1580	}
1581	}
1582
1583
1584	assert(!NonLocalDeps.count(RemInst) && "RemInst got reinserted?")((!NonLocalDeps.count(RemInst) && "RemInst got reinserted?" ) ? static_cast<void> (0) : __assert_fail ("!NonLocalDeps.count(RemInst) && \"RemInst got reinserted?\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.6~svn224456/lib/Analysis/MemoryDependenceAnalysis.cpp" , 1584, __PRETTY_FUNCTION__));
1585	AA->deleteValue(RemInst);
1586	DEBUG(verifyRemoved(RemInst))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("memdep")) { verifyRemoved(RemInst); } } while (0);
1587	}
1588	/// verifyRemoved - Verify that the specified instruction does not occur
1589	/// in our internal data structures. This function verifies by asserting in
1590	/// debug builds.
1591	void MemoryDependenceAnalysis::verifyRemoved(Instruction *D) const {
1592	#ifndef NDEBUG
1593	for (LocalDepMapType::const_iterator I = LocalDeps.begin(),
1594	E = LocalDeps.end(); I != E; ++I) {
1595	assert(I->first != D && "Inst occurs in data structures")((I->first != D && "Inst occurs in data structures" ) ? static_cast<void> (0) : __assert_fail ("I->first != D && \"Inst occurs in data structures\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.6~svn224456/lib/Analysis/MemoryDependenceAnalysis.cpp" , 1595, __PRETTY_FUNCTION__));
1596	assert(I->second.getInst() != D &&((I->second.getInst() != D && "Inst occurs in data structures" ) ? static_cast<void> (0) : __assert_fail ("I->second.getInst() != D && \"Inst occurs in data structures\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.6~svn224456/lib/Analysis/MemoryDependenceAnalysis.cpp" , 1597, __PRETTY_FUNCTION__))
1597	"Inst occurs in data structures")((I->second.getInst() != D && "Inst occurs in data structures" ) ? static_cast<void> (0) : __assert_fail ("I->second.getInst() != D && \"Inst occurs in data structures\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.6~svn224456/lib/Analysis/MemoryDependenceAnalysis.cpp" , 1597, __PRETTY_FUNCTION__));
1598	}
1599
1600	for (CachedNonLocalPointerInfo::const_iterator I =NonLocalPointerDeps.begin(),
1601	E = NonLocalPointerDeps.end(); I != E; ++I) {
1602	assert(I->first.getPointer() != D && "Inst occurs in NLPD map key")((I->first.getPointer() != D && "Inst occurs in NLPD map key" ) ? static_cast<void> (0) : __assert_fail ("I->first.getPointer() != D && \"Inst occurs in NLPD map key\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.6~svn224456/lib/Analysis/MemoryDependenceAnalysis.cpp" , 1602, __PRETTY_FUNCTION__));
1603	const NonLocalDepInfo &Val = I->second.NonLocalDeps;
1604	for (NonLocalDepInfo::const_iterator II = Val.begin(), E = Val.end();
1605	II != E; ++II)
1606	assert(II->getResult().getInst() != D && "Inst occurs as NLPD value")((II->getResult().getInst() != D && "Inst occurs as NLPD value" ) ? static_cast<void> (0) : __assert_fail ("II->getResult().getInst() != D && \"Inst occurs as NLPD value\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.6~svn224456/lib/Analysis/MemoryDependenceAnalysis.cpp" , 1606, __PRETTY_FUNCTION__));
1607	}
1608
1609	for (NonLocalDepMapType::const_iterator I = NonLocalDeps.begin(),
1610	E = NonLocalDeps.end(); I != E; ++I) {
1611	assert(I->first != D && "Inst occurs in data structures")((I->first != D && "Inst occurs in data structures" ) ? static_cast<void> (0) : __assert_fail ("I->first != D && \"Inst occurs in data structures\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.6~svn224456/lib/Analysis/MemoryDependenceAnalysis.cpp" , 1611, __PRETTY_FUNCTION__));
1612	const PerInstNLInfo &INLD = I->second;
1613	for (NonLocalDepInfo::const_iterator II = INLD.first.begin(),
1614	EE = INLD.first.end(); II != EE; ++II)
1615	assert(II->getResult().getInst() != D && "Inst occurs in data structures")((II->getResult().getInst() != D && "Inst occurs in data structures" ) ? static_cast<void> (0) : __assert_fail ("II->getResult().getInst() != D && \"Inst occurs in data structures\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.6~svn224456/lib/Analysis/MemoryDependenceAnalysis.cpp" , 1615, __PRETTY_FUNCTION__));
1616	}
1617
1618	for (ReverseDepMapType::const_iterator I = ReverseLocalDeps.begin(),
1619	E = ReverseLocalDeps.end(); I != E; ++I) {
1620	assert(I->first != D && "Inst occurs in data structures")((I->first != D && "Inst occurs in data structures" ) ? static_cast<void> (0) : __assert_fail ("I->first != D && \"Inst occurs in data structures\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.6~svn224456/lib/Analysis/MemoryDependenceAnalysis.cpp" , 1620, __PRETTY_FUNCTION__));
1621	for (Instruction *Inst : I->second)
1622	assert(Inst != D && "Inst occurs in data structures")((Inst != D && "Inst occurs in data structures") ? static_cast <void> (0) : __assert_fail ("Inst != D && \"Inst occurs in data structures\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.6~svn224456/lib/Analysis/MemoryDependenceAnalysis.cpp" , 1622, __PRETTY_FUNCTION__));
1623	}
1624
1625	for (ReverseDepMapType::const_iterator I = ReverseNonLocalDeps.begin(),
1626	E = ReverseNonLocalDeps.end();
1627	I != E; ++I) {
1628	assert(I->first != D && "Inst occurs in data structures")((I->first != D && "Inst occurs in data structures" ) ? static_cast<void> (0) : __assert_fail ("I->first != D && \"Inst occurs in data structures\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.6~svn224456/lib/Analysis/MemoryDependenceAnalysis.cpp" , 1628, __PRETTY_FUNCTION__));
1629	for (Instruction *Inst : I->second)
1630	assert(Inst != D && "Inst occurs in data structures")((Inst != D && "Inst occurs in data structures") ? static_cast <void> (0) : __assert_fail ("Inst != D && \"Inst occurs in data structures\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.6~svn224456/lib/Analysis/MemoryDependenceAnalysis.cpp" , 1630, __PRETTY_FUNCTION__));
1631	}
1632
1633	for (ReverseNonLocalPtrDepTy::const_iterator
1634	I = ReverseNonLocalPtrDeps.begin(),
1635	E = ReverseNonLocalPtrDeps.end(); I != E; ++I) {
1636	assert(I->first != D && "Inst occurs in rev NLPD map")((I->first != D && "Inst occurs in rev NLPD map") ? static_cast<void> (0) : __assert_fail ("I->first != D && \"Inst occurs in rev NLPD map\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.6~svn224456/lib/Analysis/MemoryDependenceAnalysis.cpp" , 1636, __PRETTY_FUNCTION__));
1637
1638	for (ValueIsLoadPair P : I->second)
1639	assert(P != ValueIsLoadPair(D, false) &&((P != ValueIsLoadPair(D, false) && P != ValueIsLoadPair (D, true) && "Inst occurs in ReverseNonLocalPtrDeps map" ) ? static_cast<void> (0) : __assert_fail ("P != ValueIsLoadPair(D, false) && P != ValueIsLoadPair(D, true) && \"Inst occurs in ReverseNonLocalPtrDeps map\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.6~svn224456/lib/Analysis/MemoryDependenceAnalysis.cpp" , 1641, __PRETTY_FUNCTION__))
1640	P != ValueIsLoadPair(D, true) &&((P != ValueIsLoadPair(D, false) && P != ValueIsLoadPair (D, true) && "Inst occurs in ReverseNonLocalPtrDeps map" ) ? static_cast<void> (0) : __assert_fail ("P != ValueIsLoadPair(D, false) && P != ValueIsLoadPair(D, true) && \"Inst occurs in ReverseNonLocalPtrDeps map\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.6~svn224456/lib/Analysis/MemoryDependenceAnalysis.cpp" , 1641, __PRETTY_FUNCTION__))
1641	"Inst occurs in ReverseNonLocalPtrDeps map")((P != ValueIsLoadPair(D, false) && P != ValueIsLoadPair (D, true) && "Inst occurs in ReverseNonLocalPtrDeps map" ) ? static_cast<void> (0) : __assert_fail ("P != ValueIsLoadPair(D, false) && P != ValueIsLoadPair(D, true) && \"Inst occurs in ReverseNonLocalPtrDeps map\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.6~svn224456/lib/Analysis/MemoryDependenceAnalysis.cpp" , 1641, __PRETTY_FUNCTION__));
1642	}
1643	#endif
1644	}