1	//===- Attributor.h --- Module-wide attribute deduction ---------*- C++ -*-===//
2	//
3	// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4	// See https://llvm.org/LICENSE.txt for license information.
5	// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6	//
7	//===----------------------------------------------------------------------===//
8	//
9	// Attributor: An inter procedural (abstract) "attribute" deduction framework.
10	//
11	// The Attributor framework is an inter procedural abstract analysis (fixpoint
12	// iteration analysis). The goal is to allow easy deduction of new attributes as
13	// well as information exchange between abstract attributes in-flight.
14	//
15	// The Attributor class is the driver and the link between the various abstract
16	// attributes. The Attributor will iterate until a fixpoint state is reached by
17	// all abstract attributes in-flight, or until it will enforce a pessimistic fix
18	// point because an iteration limit is reached.
19	//
20	// Abstract attributes, derived from the AbstractAttribute class, actually
21	// describe properties of the code. They can correspond to actual LLVM-IR
22	// attributes, or they can be more general, ultimately unrelated to LLVM-IR
23	// attributes. The latter is useful when an abstract attributes provides
24	// information to other abstract attributes in-flight but we might not want to
25	// manifest the information. The Attributor allows to query in-flight abstract
26	// attributes through the `Attributor::getAAFor` method (see the method
27	// description for an example). If the method is used by an abstract attribute
28	// P, and it results in an abstract attribute Q, the Attributor will
29	// automatically capture a potential dependence from Q to P. This dependence
30	// will cause P to be reevaluated whenever Q changes in the future.
31	//
32	// The Attributor will only reevaluate abstract attributes that might have
33	// changed since the last iteration. That means that the Attribute will not
34	// revisit all instructions/blocks/functions in the module but only query
35	// an update from a subset of the abstract attributes.
36	//
37	// The update method `AbstractAttribute::updateImpl` is implemented by the
38	// specific "abstract attribute" subclasses. The method is invoked whenever the
39	// currently assumed state (see the AbstractState class) might not be valid
40	// anymore. This can, for example, happen if the state was dependent on another
41	// abstract attribute that changed. In every invocation, the update method has
42	// to adjust the internal state of an abstract attribute to a point that is
43	// justifiable by the underlying IR and the current state of abstract attributes
44	// in-flight. Since the IR is given and assumed to be valid, the information
45	// derived from it can be assumed to hold. However, information derived from
46	// other abstract attributes is conditional on various things. If the justifying
47	// state changed, the `updateImpl` has to revisit the situation and potentially
48	// find another justification or limit the optimistic assumes made.
49	//
50	// Change is the key in this framework. Until a state of no-change, thus a
51	// fixpoint, is reached, the Attributor will query the abstract attributes
52	// in-flight to re-evaluate their state. If the (current) state is too
53	// optimistic, hence it cannot be justified anymore through other abstract
54	// attributes or the state of the IR, the state of the abstract attribute will
55	// have to change. Generally, we assume abstract attribute state to be a finite
56	// height lattice and the update function to be monotone. However, these
57	// conditions are not enforced because the iteration limit will guarantee
58	// termination. If an optimistic fixpoint is reached, or a pessimistic fix
59	// point is enforced after a timeout, the abstract attributes are tasked to
60	// manifest their result in the IR for passes to come.
61	//
62	// Attribute manifestation is not mandatory. If desired, there is support to
63	// generate a single or multiple LLVM-IR attributes already in the helper struct
64	// IRAttribute. In the simplest case, a subclass inherits from IRAttribute with
65	// a proper Attribute::AttrKind as template parameter. The Attributor
66	// manifestation framework will then create and place a new attribute if it is
67	// allowed to do so (based on the abstract state). Other use cases can be
68	// achieved by overloading AbstractAttribute or IRAttribute methods.
69	//
70	//
71	// The "mechanics" of adding a new "abstract attribute":
72	// - Define a class (transitively) inheriting from AbstractAttribute and one
73	// (which could be the same) that (transitively) inherits from AbstractState.
74	// For the latter, consider the already available BooleanState and
75	// {Inc,Dec,Bit}IntegerState if they fit your needs, e.g., you require only a
76	// number tracking or bit-encoding.
77	// - Implement all pure methods. Also use overloading if the attribute is not
78	// conforming with the "default" behavior: A (set of) LLVM-IR attribute(s) for
79	// an argument, call site argument, function return value, or function. See
80	// the class and method descriptions for more information on the two
81	// "Abstract" classes and their respective methods.
82	// - Register opportunities for the new abstract attribute in the
83	// `Attributor::identifyDefaultAbstractAttributes` method if it should be
84	// counted as a 'default' attribute.
85	// - Add sufficient tests.
86	// - Add a Statistics object for bookkeeping. If it is a simple (set of)
87	// attribute(s) manifested through the Attributor manifestation framework, see
88	// the bookkeeping function in Attributor.cpp.
89	// - If instructions with a certain opcode are interesting to the attribute, add
90	// that opcode to the switch in `Attributor::identifyAbstractAttributes`. This
91	// will make it possible to query all those instructions through the
92	// `InformationCache::getOpcodeInstMapForFunction` interface and eliminate the
93	// need to traverse the IR repeatedly.
94	//
95	//===----------------------------------------------------------------------===//
96
97	#ifndef LLVM_TRANSFORMS_IPO_ATTRIBUTOR_H
98	#define LLVM_TRANSFORMS_IPO_ATTRIBUTOR_H
99
100	#include "llvm/ADT/DenseSet.h"
101	#include "llvm/ADT/GraphTraits.h"
102	#include "llvm/ADT/MapVector.h"
103	#include "llvm/ADT/STLExtras.h"
104	#include "llvm/ADT/SetOperations.h"
105	#include "llvm/ADT/SetVector.h"
106	#include "llvm/ADT/SmallSet.h"
107	#include "llvm/ADT/iterator.h"
108	#include "llvm/Analysis/AssumeBundleQueries.h"
109	#include "llvm/Analysis/CFG.h"
110	#include "llvm/Analysis/CGSCCPassManager.h"
111	#include "llvm/Analysis/LazyCallGraph.h"
112	#include "llvm/Analysis/LoopInfo.h"
113	#include "llvm/Analysis/MemoryLocation.h"
114	#include "llvm/Analysis/MustExecute.h"
115	#include "llvm/Analysis/OptimizationRemarkEmitter.h"
116	#include "llvm/Analysis/PostDominators.h"
117	#include "llvm/Analysis/TargetLibraryInfo.h"
118	#include "llvm/IR/AbstractCallSite.h"
119	#include "llvm/IR/Attributes.h"
120	#include "llvm/IR/ConstantRange.h"
121	#include "llvm/IR/Constants.h"
122	#include "llvm/IR/GlobalValue.h"
123	#include "llvm/IR/InstIterator.h"
124	#include "llvm/IR/Instruction.h"
125	#include "llvm/IR/Instructions.h"
126	#include "llvm/IR/PassManager.h"
127	#include "llvm/IR/Value.h"
128	#include "llvm/Support/Alignment.h"
129	#include "llvm/Support/Allocator.h"
130	#include "llvm/Support/Casting.h"
131	#include "llvm/Support/DOTGraphTraits.h"
132	#include "llvm/Support/DebugCounter.h"
133	#include "llvm/Support/ErrorHandling.h"
134	#include "llvm/Support/ModRef.h"
135	#include "llvm/Support/TimeProfiler.h"
136	#include "llvm/Support/TypeSize.h"
137	#include "llvm/TargetParser/Triple.h"
138	#include "llvm/Transforms/Utils/CallGraphUpdater.h"
139
140	#include <limits>
141	#include <map>
142	#include <optional>
143
144	namespace llvm {
145
146	class DataLayout;
147	class LLVMContext;
148	class Pass;
149	template <typename Fn> class function_ref;
150	struct AADepGraphNode;
151	struct AADepGraph;
152	struct Attributor;
153	struct AbstractAttribute;
154	struct InformationCache;
155	struct AAIsDead;
156	struct AttributorCallGraph;
157	struct IRPosition;
158
159	class Function;
160
161	/// Abstract Attribute helper functions.
162	namespace AA {
163	using InstExclusionSetTy = SmallPtrSet<Instruction *, 4>;
164
165	enum class GPUAddressSpace : unsigned {
166	Generic = 0,
167	Global = 1,
168	Shared = 3,
169	Constant = 4,
170	Local = 5,
171	};
172
173	/// Return true iff \p M target a GPU (and we can use GPU AS reasoning).
174	bool isGPU(const Module &M);
175
176	/// Flags to distinguish intra-procedural queries from *potentially*
177	/// inter-procedural queries. Not that information can be valid for both and
178	/// therefore both bits might be set.
179	enum ValueScope : uint8_t {
180	Intraprocedural = 1,
181	Interprocedural = 2,
182	AnyScope = Intraprocedural | Interprocedural,
183	};
184
185	struct ValueAndContext : public std::pair<Value *, const Instruction *> {
186	using Base = std::pair<Value *, const Instruction *>;
187	ValueAndContext(const Base &B) : Base(B) {}
188	ValueAndContext(Value &V, const Instruction *CtxI) : Base(&V, CtxI) {}
189	ValueAndContext(Value &V, const Instruction &CtxI) : Base(&V, &CtxI) {}
190
191	Value *getValue() const { return this->first; }
192	const Instruction *getCtxI() const { return this->second; }
193	};
194
195	/// Return true if \p I is a `nosync` instruction. Use generic reasoning and
196	/// potentially the corresponding AANoSync.
197	bool isNoSyncInst(Attributor &A, const Instruction &I,
198	const AbstractAttribute &QueryingAA);
199
200	/// Return true if \p V is dynamically unique, that is, there are no two
201	/// "instances" of \p V at runtime with different values.
202	/// Note: If \p ForAnalysisOnly is set we only check that the Attributor will
203	/// never use \p V to represent two "instances" not that \p V could not
204	/// technically represent them.
205	bool isDynamicallyUnique(Attributor &A, const AbstractAttribute &QueryingAA,
206	const Value &V, bool ForAnalysisOnly = true);
207
208	/// Return true if \p V is a valid value in \p Scope, that is a constant or an
209	/// instruction/argument of \p Scope.
210	bool isValidInScope(const Value &V, const Function *Scope);
211
212	/// Return true if the value of \p VAC is a valid at the position of \p VAC,
213	/// that is a constant, an argument of the same function, or an instruction in
214	/// that function that dominates the position.
215	bool isValidAtPosition(const ValueAndContext &VAC, InformationCache &InfoCache);
216
217	/// Try to convert \p V to type \p Ty without introducing new instructions. If
218	/// this is not possible return `nullptr`. Note: this function basically knows
219	/// how to cast various constants.
220	Value *getWithType(Value &V, Type &Ty);
221
222	/// Return the combination of \p A and \p B such that the result is a possible
223	/// value of both. \p B is potentially casted to match the type \p Ty or the
224	/// type of \p A if \p Ty is null.
225	///
226	/// Examples:
227	/// X + none => X
228	/// not_none + undef => not_none
229	/// V1 + V2 => nullptr
230	std::optional<Value *>
231	combineOptionalValuesInAAValueLatice(const std::optional<Value *> &A,
232	const std::optional<Value *> &B, Type *Ty);
233
234	/// Helper to represent an access offset and size, with logic to deal with
235	/// uncertainty and check for overlapping accesses.
236	struct RangeTy {
237	int64_t Offset = Unassigned;
238	int64_t Size = Unassigned;
239
240	RangeTy(int64_t Offset, int64_t Size) : Offset(Offset), Size(Size) {}
241	RangeTy() = default;
242	static RangeTy getUnknown() { return RangeTy{Unknown, Unknown}; }
243
244	/// Return true if offset or size are unknown.
245	bool offsetOrSizeAreUnknown() const {
246	return Offset == RangeTy::Unknown || Size == RangeTy::Unknown;
247	}
248
249	/// Return true if offset and size are unknown, thus this is the default
250	/// unknown object.
251	bool offsetAndSizeAreUnknown() const {
252	return Offset == RangeTy::Unknown && Size == RangeTy::Unknown;
253	}
254
255	/// Return true if the offset and size are unassigned.
256	bool isUnassigned() const {
257	assert((Offset == RangeTy::Unassigned) == (Size == RangeTy::Unassigned) &&
258	"Inconsistent state!");
259	return Offset == RangeTy::Unassigned;
260	}
261
262	/// Return true if this offset and size pair might describe an address that
263	/// overlaps with \p Range.
264	bool mayOverlap(const RangeTy &Range) const {
265	// Any unknown value and we are giving up -> overlap.
266	if (offsetOrSizeAreUnknown() || Range.offsetOrSizeAreUnknown())
267	return true;
268
269	// Check if one offset point is in the other interval [offset,
270	// offset+size].
271	return Range.Offset + Range.Size > Offset && Range.Offset < Offset + Size;
272	}
273
274	RangeTy &operator&=(const RangeTy &R) {
275	if (R.isUnassigned())
276	return *this;
277	if (isUnassigned())
278	return *this = R;
279	if (Offset == Unknown || R.Offset == Unknown)
280	Offset = Unknown;
281	if (Size == Unknown || R.Size == Unknown)
282	Size = Unknown;
283	if (offsetAndSizeAreUnknown())
284	return *this;
285	if (Offset == Unknown) {
286	Size = std::max(a: Size, b: R.Size);
287	} else if (Size == Unknown) {
288	Offset = std::min(a: Offset, b: R.Offset);
289	} else {
290	Offset = std::min(a: Offset, b: R.Offset);
291	Size = std::max(a: Offset + Size, b: R.Offset + R.Size) - Offset;
292	}
293	return *this;
294	}
295
296	/// Comparison for sorting ranges by offset.
297	///
298	/// Returns true if the offset \p L is less than that of \p R.
299	inline static bool OffsetLessThan(const RangeTy &L, const RangeTy &R) {
300	return L.Offset < R.Offset;
301	}
302
303	/// Constants used to represent special offsets or sizes.
304	/// - We cannot assume that Offsets and Size are non-negative.
305	/// - The constants should not clash with DenseMapInfo, such as EmptyKey
306	/// (INT64_MAX) and TombstoneKey (INT64_MIN).
307	/// We use values "in the middle" of the 64 bit range to represent these
308	/// special cases.
309	static constexpr int64_t Unassigned = std::numeric_limits<int32_t>::min();
310	static constexpr int64_t Unknown = std::numeric_limits<int32_t>::max();
311	};
312
313	inline raw_ostream &operator<<(raw_ostream &OS, const RangeTy &R) {
314	OS << "[" << R.Offset << ", " << R.Size << "]";
315	return OS;
316	}
317
318	inline bool operator==(const RangeTy &A, const RangeTy &B) {
319	return A.Offset == B.Offset && A.Size == B.Size;
320	}
321
322	inline bool operator!=(const RangeTy &A, const RangeTy &B) { return !(A == B); }
323
324	/// Return the initial value of \p Obj with type \p Ty if that is a constant.
325	Constant *getInitialValueForObj(Attributor &A,
326	const AbstractAttribute &QueryingAA, Value &Obj,
327	Type &Ty, const TargetLibraryInfo *TLI,
328	const DataLayout &DL,
329	RangeTy *RangePtr = nullptr);
330
331	/// Collect all potential values \p LI could read into \p PotentialValues. That
332	/// is, the only values read by \p LI are assumed to be known and all are in
333	/// \p PotentialValues. \p PotentialValueOrigins will contain all the
334	/// instructions that might have put a potential value into \p PotentialValues.
335	/// Dependences onto \p QueryingAA are properly tracked, \p
336	/// UsedAssumedInformation will inform the caller if assumed information was
337	/// used.
338	///
339	/// \returns True if the assumed potential copies are all in \p PotentialValues,
340	/// false if something went wrong and the copies could not be
341	/// determined.
342	bool getPotentiallyLoadedValues(
343	Attributor &A, LoadInst &LI, SmallSetVector<Value *, 4> &PotentialValues,
344	SmallSetVector<Instruction *, 4> &PotentialValueOrigins,
345	const AbstractAttribute &QueryingAA, bool &UsedAssumedInformation,
346	bool OnlyExact = false);
347
348	/// Collect all potential values of the one stored by \p SI into
349	/// \p PotentialCopies. That is, the only copies that were made via the
350	/// store are assumed to be known and all are in \p PotentialCopies. Dependences
351	/// onto \p QueryingAA are properly tracked, \p UsedAssumedInformation will
352	/// inform the caller if assumed information was used.
353	///
354	/// \returns True if the assumed potential copies are all in \p PotentialCopies,
355	/// false if something went wrong and the copies could not be
356	/// determined.
357	bool getPotentialCopiesOfStoredValue(
358	Attributor &A, StoreInst &SI, SmallSetVector<Value *, 4> &PotentialCopies,
359	const AbstractAttribute &QueryingAA, bool &UsedAssumedInformation,
360	bool OnlyExact = false);
361
362	/// Return true if \p IRP is readonly. This will query respective AAs that
363	/// deduce the information and introduce dependences for \p QueryingAA.
364	bool isAssumedReadOnly(Attributor &A, const IRPosition &IRP,
365	const AbstractAttribute &QueryingAA, bool &IsKnown);
366
367	/// Return true if \p IRP is readnone. This will query respective AAs that
368	/// deduce the information and introduce dependences for \p QueryingAA.
369	bool isAssumedReadNone(Attributor &A, const IRPosition &IRP,
370	const AbstractAttribute &QueryingAA, bool &IsKnown);
371
372	/// Return true if \p ToI is potentially reachable from \p FromI without running
373	/// into any instruction in \p ExclusionSet The two instructions do not need to
374	/// be in the same function. \p GoBackwardsCB can be provided to convey domain
375	/// knowledge about the "lifespan" the user is interested in. By default, the
376	/// callers of \p FromI are checked as well to determine if \p ToI can be
377	/// reached. If the query is not interested in callers beyond a certain point,
378	/// e.g., a GPU kernel entry or the function containing an alloca, the
379	/// \p GoBackwardsCB should return false.
380	bool isPotentiallyReachable(
381	Attributor &A, const Instruction &FromI, const Instruction &ToI,
382	const AbstractAttribute &QueryingAA,
383	const AA::InstExclusionSetTy *ExclusionSet = nullptr,
384	std::function<bool(const Function &F)> GoBackwardsCB = nullptr);
385
386	/// Same as above but it is sufficient to reach any instruction in \p ToFn.
387	bool isPotentiallyReachable(
388	Attributor &A, const Instruction &FromI, const Function &ToFn,
389	const AbstractAttribute &QueryingAA,
390	const AA::InstExclusionSetTy *ExclusionSet = nullptr,
391	std::function<bool(const Function &F)> GoBackwardsCB = nullptr);
392
393	/// Return true if \p Obj is assumed to be a thread local object.
394	bool isAssumedThreadLocalObject(Attributor &A, Value &Obj,
395	const AbstractAttribute &QueryingAA);
396
397	/// Return true if \p I is potentially affected by a barrier.
398	bool isPotentiallyAffectedByBarrier(Attributor &A, const Instruction &I,
399	const AbstractAttribute &QueryingAA);
400	bool isPotentiallyAffectedByBarrier(Attributor &A, ArrayRef<const Value *> Ptrs,
401	const AbstractAttribute &QueryingAA,
402	const Instruction *CtxI);
403	} // namespace AA
404
405	template <>
406	struct DenseMapInfo<AA::ValueAndContext>
407	: public DenseMapInfo<AA::ValueAndContext::Base> {
408	using Base = DenseMapInfo<AA::ValueAndContext::Base>;
409	static inline AA::ValueAndContext getEmptyKey() {
410	return Base::getEmptyKey();
411	}
412	static inline AA::ValueAndContext getTombstoneKey() {
413	return Base::getTombstoneKey();
414	}
415	static unsigned getHashValue(const AA::ValueAndContext &VAC) {
416	return Base::getHashValue(PairVal: VAC);
417	}
418
419	static bool isEqual(const AA::ValueAndContext &LHS,
420	const AA::ValueAndContext &RHS) {
421	return Base::isEqual(LHS, RHS);
422	}
423	};
424
425	template <>
426	struct DenseMapInfo<AA::ValueScope> : public DenseMapInfo<unsigned char> {
427	using Base = DenseMapInfo<unsigned char>;
428	static inline AA::ValueScope getEmptyKey() {
429	return AA::ValueScope(Base::getEmptyKey());
430	}
431	static inline AA::ValueScope getTombstoneKey() {
432	return AA::ValueScope(Base::getTombstoneKey());
433	}
434	static unsigned getHashValue(const AA::ValueScope &S) {
435	return Base::getHashValue(Val: S);
436	}
437
438	static bool isEqual(const AA::ValueScope &LHS, const AA::ValueScope &RHS) {
439	return Base::isEqual(LHS, RHS);
440	}
441	};
442
443	template <>
444	struct DenseMapInfo<const AA::InstExclusionSetTy *>
445	: public DenseMapInfo<void *> {
446	using super = DenseMapInfo<void *>;
447	static inline const AA::InstExclusionSetTy *getEmptyKey() {
448	return static_cast<const AA::InstExclusionSetTy *>(super::getEmptyKey());
449	}
450	static inline const AA::InstExclusionSetTy *getTombstoneKey() {
451	return static_cast<const AA::InstExclusionSetTy *>(
452	super::getTombstoneKey());
453	}
454	static unsigned getHashValue(const AA::InstExclusionSetTy *BES) {
455	unsigned H = 0;
456	if (BES)
457	for (const auto *II : *BES)
458	H += DenseMapInfo<const Instruction *>::getHashValue(PtrVal: II);
459	return H;
460	}
461	static bool isEqual(const AA::InstExclusionSetTy *LHS,
462	const AA::InstExclusionSetTy *RHS) {
463	if (LHS == RHS)
464	return true;
465	if (LHS == getEmptyKey() || RHS == getEmptyKey() ||
466	LHS == getTombstoneKey() || RHS == getTombstoneKey())
467	return false;
468	auto SizeLHS = LHS ? LHS->size() : 0;
469	auto SizeRHS = RHS ? RHS->size() : 0;
470	if (SizeLHS != SizeRHS)
471	return false;
472	if (SizeRHS == 0)
473	return true;
474	return llvm::set_is_subset(S1: *LHS, S2: *RHS);
475	}
476	};
477
478	/// The value passed to the line option that defines the maximal initialization
479	/// chain length.
480	extern unsigned MaxInitializationChainLength;
481
482	///{
483	enum class ChangeStatus {
484	CHANGED,
485	UNCHANGED,
486	};
487
488	ChangeStatus operator|(ChangeStatus l, ChangeStatus r);
489	ChangeStatus &operator|=(ChangeStatus &l, ChangeStatus r);
490	ChangeStatus operator&(ChangeStatus l, ChangeStatus r);
491	ChangeStatus &operator&=(ChangeStatus &l, ChangeStatus r);
492
493	enum class DepClassTy {
494	REQUIRED, ///< The target cannot be valid if the source is not.
495	OPTIONAL, ///< The target may be valid if the source is not.
496	NONE, ///< Do not track a dependence between source and target.
497	};
498	///}
499
500	/// The data structure for the nodes of a dependency graph
501	struct AADepGraphNode {
502	public:
503	virtual ~AADepGraphNode() = default;
504	using DepTy = PointerIntPair<AADepGraphNode *, 1>;
505	using DepSetTy = SmallSetVector<DepTy, 2>;
506
507	protected:
508	/// Set of dependency graph nodes which should be updated if this one
509	/// is updated. The bit encodes if it is optional.
510	DepSetTy Deps;
511
512	static AADepGraphNode *DepGetVal(const DepTy &DT) { return DT.getPointer(); }
513	static AbstractAttribute *DepGetValAA(const DepTy &DT) {
514	return cast<AbstractAttribute>(Val: DT.getPointer());
515	}
516
517	operator AbstractAttribute *() { return cast<AbstractAttribute>(Val: this); }
518
519	public:
520	using iterator = mapped_iterator<DepSetTy::iterator, decltype(&DepGetVal)>;
521	using aaiterator =
522	mapped_iterator<DepSetTy::iterator, decltype(&DepGetValAA)>;
523
524	aaiterator begin() { return aaiterator(Deps.begin(), &DepGetValAA); }
525	aaiterator end() { return aaiterator(Deps.end(), &DepGetValAA); }
526	iterator child_begin() { return iterator(Deps.begin(), &DepGetVal); }
527	iterator child_end() { return iterator(Deps.end(), &DepGetVal); }
528
529	void print(raw_ostream &OS) const { print(nullptr, OS); }
530	virtual void print(Attributor *, raw_ostream &OS) const {
531	OS << "AADepNode Impl\n";
532	}
533	DepSetTy &getDeps() { return Deps; }
534
535	friend struct Attributor;
536	friend struct AADepGraph;
537	};
538
539	/// The data structure for the dependency graph
540	///
541	/// Note that in this graph if there is an edge from A to B (A -> B),
542	/// then it means that B depends on A, and when the state of A is
543	/// updated, node B should also be updated
544	struct AADepGraph {
545	AADepGraph() = default;
546	~AADepGraph() = default;
547
548	using DepTy = AADepGraphNode::DepTy;
549	static AADepGraphNode *DepGetVal(const DepTy &DT) { return DT.getPointer(); }
550	using iterator =
551	mapped_iterator<AADepGraphNode::DepSetTy::iterator, decltype(&DepGetVal)>;
552
553	/// There is no root node for the dependency graph. But the SCCIterator
554	/// requires a single entry point, so we maintain a fake("synthetic") root
555	/// node that depends on every node.
556	AADepGraphNode SyntheticRoot;
557	AADepGraphNode *GetEntryNode() { return &SyntheticRoot; }
558
559	iterator begin() { return SyntheticRoot.child_begin(); }
560	iterator end() { return SyntheticRoot.child_end(); }
561
562	void viewGraph();
563
564	/// Dump graph to file
565	void dumpGraph();
566
567	/// Print dependency graph
568	void print();
569	};
570
571	/// Helper to describe and deal with positions in the LLVM-IR.
572	///
573	/// A position in the IR is described by an anchor value and an "offset" that
574	/// could be the argument number, for call sites and arguments, or an indicator
575	/// of the "position kind". The kinds, specified in the Kind enum below, include
576	/// the locations in the attribute list, i.a., function scope and return value,
577	/// as well as a distinction between call sites and functions. Finally, there
578	/// are floating values that do not have a corresponding attribute list
579	/// position.
580	struct IRPosition {
581	// NOTE: In the future this definition can be changed to support recursive
582	// functions.
583	using CallBaseContext = CallBase;
584
585	/// The positions we distinguish in the IR.
586	enum Kind : char {
587	IRP_INVALID, ///< An invalid position.
588	IRP_FLOAT, ///< A position that is not associated with a spot suitable
589	///< for attributes. This could be any value or instruction.
590	IRP_RETURNED, ///< An attribute for the function return value.
591	IRP_CALL_SITE_RETURNED, ///< An attribute for a call site return value.
592	IRP_FUNCTION, ///< An attribute for a function (scope).
593	IRP_CALL_SITE, ///< An attribute for a call site (function scope).
594	IRP_ARGUMENT, ///< An attribute for a function argument.
595	IRP_CALL_SITE_ARGUMENT, ///< An attribute for a call site argument.
596	};
597
598	/// Default constructor available to create invalid positions implicitly. All
599	/// other positions need to be created explicitly through the appropriate
600	/// static member function.
601	IRPosition() : Enc(nullptr, ENC_VALUE) { verify(); }
602
603	/// Create a position describing the value of \p V.
604	static const IRPosition value(const Value &V,
605	const CallBaseContext *CBContext = nullptr) {
606	if (auto *Arg = dyn_cast<Argument>(Val: &V))
607	return IRPosition::argument(Arg: *Arg, CBContext);
608	if (auto *CB = dyn_cast<CallBase>(Val: &V))
609	return IRPosition::callsite_returned(CB: *CB);
610	return IRPosition(const_cast<Value &>(V), IRP_FLOAT, CBContext);
611	}
612
613	/// Create a position describing the instruction \p I. This is different from
614	/// the value version because call sites are treated as intrusctions rather
615	/// than their return value in this function.
616	static const IRPosition inst(const Instruction &I,
617	const CallBaseContext *CBContext = nullptr) {
618	return IRPosition(const_cast<Instruction &>(I), IRP_FLOAT, CBContext);
619	}
620
621	/// Create a position describing the function scope of \p F.
622	/// \p CBContext is used for call base specific analysis.
623	static const IRPosition function(const Function &F,
624	const CallBaseContext *CBContext = nullptr) {
625	return IRPosition(const_cast<Function &>(F), IRP_FUNCTION, CBContext);
626	}
627
628	/// Create a position describing the returned value of \p F.
629	/// \p CBContext is used for call base specific analysis.
630	static const IRPosition returned(const Function &F,
631	const CallBaseContext *CBContext = nullptr) {
632	return IRPosition(const_cast<Function &>(F), IRP_RETURNED, CBContext);
633	}
634
635	/// Create a position describing the argument \p Arg.
636	/// \p CBContext is used for call base specific analysis.
637	static const IRPosition argument(const Argument &Arg,
638	const CallBaseContext *CBContext = nullptr) {
639	return IRPosition(const_cast<Argument &>(Arg), IRP_ARGUMENT, CBContext);
640	}
641
642	/// Create a position describing the function scope of \p CB.
643	static const IRPosition callsite_function(const CallBase &CB) {
644	return IRPosition(const_cast<CallBase &>(CB), IRP_CALL_SITE);
645	}
646
647	/// Create a position describing the returned value of \p CB.
648	static const IRPosition callsite_returned(const CallBase &CB) {
649	return IRPosition(const_cast<CallBase &>(CB), IRP_CALL_SITE_RETURNED);
650	}
651
652	/// Create a position describing the argument of \p CB at position \p ArgNo.
653	static const IRPosition callsite_argument(const CallBase &CB,
654	unsigned ArgNo) {
655	return IRPosition(const_cast<Use &>(CB.getArgOperandUse(i: ArgNo)),
656	IRP_CALL_SITE_ARGUMENT);
657	}
658
659	/// Create a position describing the argument of \p ACS at position \p ArgNo.
660	static const IRPosition callsite_argument(AbstractCallSite ACS,
661	unsigned ArgNo) {
662	if (ACS.getNumArgOperands() <= ArgNo)
663	return IRPosition();
664	int CSArgNo = ACS.getCallArgOperandNo(ArgNo);
665	if (CSArgNo >= 0)
666	return IRPosition::callsite_argument(
667	CB: cast<CallBase>(Val&: *ACS.getInstruction()), ArgNo: CSArgNo);
668	return IRPosition();
669	}
670
671	/// Create a position with function scope matching the "context" of \p IRP.
672	/// If \p IRP is a call site (see isAnyCallSitePosition()) then the result
673	/// will be a call site position, otherwise the function position of the
674	/// associated function.
675	static const IRPosition
676	function_scope(const IRPosition &IRP,
677	const CallBaseContext *CBContext = nullptr) {
678	if (IRP.isAnyCallSitePosition()) {
679	return IRPosition::callsite_function(
680	CB: cast<CallBase>(Val&: IRP.getAnchorValue()));
681	}
682	assert(IRP.getAssociatedFunction());
683	return IRPosition::function(F: *IRP.getAssociatedFunction(), CBContext);
684	}
685
686	bool operator==(const IRPosition &RHS) const {
687	return Enc == RHS.Enc && RHS.CBContext == CBContext;
688	}
689	bool operator!=(const IRPosition &RHS) const { return !(*this == RHS); }
690
691	/// Return the value this abstract attribute is anchored with.
692	///
693	/// The anchor value might not be the associated value if the latter is not
694	/// sufficient to determine where arguments will be manifested. This is, so
695	/// far, only the case for call site arguments as the value is not sufficient
696	/// to pinpoint them. Instead, we can use the call site as an anchor.
697	Value &getAnchorValue() const {
698	switch (getEncodingBits()) {
699	case ENC_VALUE:
700	case ENC_RETURNED_VALUE:
701	case ENC_FLOATING_FUNCTION:
702	return *getAsValuePtr();
703	case ENC_CALL_SITE_ARGUMENT_USE:
704	return *(getAsUsePtr()->getUser());
705	default:
706	llvm_unreachable("Unkown encoding!");
707	};
708	}
709
710	/// Return the associated function, if any.
711	Function *getAssociatedFunction() const {
712	if (auto *CB = dyn_cast<CallBase>(Val: &getAnchorValue())) {
713	// We reuse the logic that associates callback calles to arguments of a
714	// call site here to identify the callback callee as the associated
715	// function.
716	if (Argument *Arg = getAssociatedArgument())
717	return Arg->getParent();
718	return dyn_cast_if_present<Function>(
719	Val: CB->getCalledOperand()->stripPointerCasts());
720	}
721	return getAnchorScope();
722	}
723
724	/// Return the associated argument, if any.
725	Argument *getAssociatedArgument() const;
726
727	/// Return true if the position refers to a function interface, that is the
728	/// function scope, the function return, or an argument.
729	bool isFnInterfaceKind() const {
730	switch (getPositionKind()) {
731	case IRPosition::IRP_FUNCTION:
732	case IRPosition::IRP_RETURNED:
733	case IRPosition::IRP_ARGUMENT:
734	return true;
735	default:
736	return false;
737	}
738	}
739
740	/// Return true if this is a function or call site position.
741	bool isFunctionScope() const {
742	switch (getPositionKind()) {
743	case IRPosition::IRP_CALL_SITE:
744	case IRPosition::IRP_FUNCTION:
745	return true;
746	default:
747	return false;
748	};
749	}
750
751	/// Return the Function surrounding the anchor value.
752	Function *getAnchorScope() const {
753	Value &V = getAnchorValue();
754	if (isa<Function>(Val: V))
755	return &cast<Function>(Val&: V);
756	if (isa<Argument>(Val: V))
757	return cast<Argument>(Val&: V).getParent();
758	if (isa<Instruction>(Val: V))
759	return cast<Instruction>(Val&: V).getFunction();
760	return nullptr;
761	}
762
763	/// Return the context instruction, if any.
764	Instruction *getCtxI() const {
765	Value &V = getAnchorValue();
766	if (auto *I = dyn_cast<Instruction>(Val: &V))
767	return I;
768	if (auto *Arg = dyn_cast<Argument>(Val: &V))
769	if (!Arg->getParent()->isDeclaration())
770	return &Arg->getParent()->getEntryBlock().front();
771	if (auto *F = dyn_cast<Function>(Val: &V))
772	if (!F->isDeclaration())
773	return &(F->getEntryBlock().front());
774	return nullptr;
775	}
776
777	/// Return the value this abstract attribute is associated with.
778	Value &getAssociatedValue() const {
779	if (getCallSiteArgNo() < 0 || isa<Argument>(Val: &getAnchorValue()))
780	return getAnchorValue();
781	assert(isa<CallBase>(&getAnchorValue()) && "Expected a call base!");
782	return *cast<CallBase>(Val: &getAnchorValue())
783	->getArgOperand(i: getCallSiteArgNo());
784	}
785
786	/// Return the type this abstract attribute is associated with.
787	Type *getAssociatedType() const {
788	if (getPositionKind() == IRPosition::IRP_RETURNED)
789	return getAssociatedFunction()->getReturnType();
790	return getAssociatedValue().getType();
791	}
792
793	/// Return the callee argument number of the associated value if it is an
794	/// argument or call site argument, otherwise a negative value. In contrast to
795	/// `getCallSiteArgNo` this method will always return the "argument number"
796	/// from the perspective of the callee. This may not the same as the call site
797	/// if this is a callback call.
798	int getCalleeArgNo() const {
799	return getArgNo(/* CallbackCalleeArgIfApplicable */ CallbackCalleeArgIfApplicable: true);
800	}
801
802	/// Return the call site argument number of the associated value if it is an
803	/// argument or call site argument, otherwise a negative value. In contrast to
804	/// `getCalleArgNo` this method will always return the "operand number" from
805	/// the perspective of the call site. This may not the same as the callee
806	/// perspective if this is a callback call.
807	int getCallSiteArgNo() const {
808	return getArgNo(/* CallbackCalleeArgIfApplicable */ CallbackCalleeArgIfApplicable: false);
809	}
810
811	/// Return the index in the attribute list for this position.
812	unsigned getAttrIdx() const {
813	switch (getPositionKind()) {
814	case IRPosition::IRP_INVALID:
815	case IRPosition::IRP_FLOAT:
816	break;
817	case IRPosition::IRP_FUNCTION:
818	case IRPosition::IRP_CALL_SITE:
819	return AttributeList::FunctionIndex;
820	case IRPosition::IRP_RETURNED:
821	case IRPosition::IRP_CALL_SITE_RETURNED:
822	return AttributeList::ReturnIndex;
823	case IRPosition::IRP_ARGUMENT:
824	return getCalleeArgNo() + AttributeList::FirstArgIndex;
825	case IRPosition::IRP_CALL_SITE_ARGUMENT:
826	return getCallSiteArgNo() + AttributeList::FirstArgIndex;
827	}
828	llvm_unreachable(
829	"There is no attribute index for a floating or invalid position!");
830	}
831
832	/// Return the value attributes are attached to.
833	Value *getAttrListAnchor() const {
834	if (auto *CB = dyn_cast<CallBase>(Val: &getAnchorValue()))
835	return CB;
836	return getAssociatedFunction();
837	}
838
839	/// Return the attributes associated with this function or call site scope.
840	AttributeList getAttrList() const {
841	if (auto *CB = dyn_cast<CallBase>(Val: &getAnchorValue()))
842	return CB->getAttributes();
843	return getAssociatedFunction()->getAttributes();
844	}
845
846	/// Update the attributes associated with this function or call site scope.
847	void setAttrList(const AttributeList &AttrList) const {
848	if (auto *CB = dyn_cast<CallBase>(Val: &getAnchorValue()))
849	return CB->setAttributes(AttrList);
850	return getAssociatedFunction()->setAttributes(AttrList);
851	}
852
853	/// Return the number of arguments associated with this function or call site
854	/// scope.
855	unsigned getNumArgs() const {
856	assert((getPositionKind() == IRP_CALL_SITE ||
857	getPositionKind() == IRP_FUNCTION) &&
858	"Only valid for function/call site positions!");
859	if (auto *CB = dyn_cast<CallBase>(Val: &getAnchorValue()))
860	return CB->arg_size();
861	return getAssociatedFunction()->arg_size();
862	}
863
864	/// Return theargument \p ArgNo associated with this function or call site
865	/// scope.
866	Value *getArg(unsigned ArgNo) const {
867	assert((getPositionKind() == IRP_CALL_SITE ||
868	getPositionKind() == IRP_FUNCTION) &&
869	"Only valid for function/call site positions!");
870	if (auto *CB = dyn_cast<CallBase>(Val: &getAnchorValue()))
871	return CB->getArgOperand(i: ArgNo);
872	return getAssociatedFunction()->getArg(i: ArgNo);
873	}
874
875	/// Return the associated position kind.
876	Kind getPositionKind() const {
877	char EncodingBits = getEncodingBits();
878	if (EncodingBits == ENC_CALL_SITE_ARGUMENT_USE)
879	return IRP_CALL_SITE_ARGUMENT;
880	if (EncodingBits == ENC_FLOATING_FUNCTION)
881	return IRP_FLOAT;
882
883	Value *V = getAsValuePtr();
884	if (!V)
885	return IRP_INVALID;
886	if (isa<Argument>(Val: V))
887	return IRP_ARGUMENT;
888	if (isa<Function>(Val: V))
889	return isReturnPosition(EncodingBits) ? IRP_RETURNED : IRP_FUNCTION;
890	if (isa<CallBase>(Val: V))
891	return isReturnPosition(EncodingBits) ? IRP_CALL_SITE_RETURNED
892	: IRP_CALL_SITE;
893	return IRP_FLOAT;
894	}
895
896	bool isAnyCallSitePosition() const {
897	switch (getPositionKind()) {
898	case IRPosition::IRP_CALL_SITE:
899	case IRPosition::IRP_CALL_SITE_RETURNED:
900	case IRPosition::IRP_CALL_SITE_ARGUMENT:
901	return true;
902	default:
903	return false;
904	}
905	}
906
907	/// Return true if the position is an argument or call site argument.
908	bool isArgumentPosition() const {
909	switch (getPositionKind()) {
910	case IRPosition::IRP_ARGUMENT:
911	case IRPosition::IRP_CALL_SITE_ARGUMENT:
912	return true;
913	default:
914	return false;
915	}
916	}
917
918	/// Return the same position without the call base context.
919	IRPosition stripCallBaseContext() const {
920	IRPosition Result = *this;
921	Result.CBContext = nullptr;
922	return Result;
923	}
924
925	/// Get the call base context from the position.
926	const CallBaseContext *getCallBaseContext() const { return CBContext; }
927
928	/// Check if the position has any call base context.
929	bool hasCallBaseContext() const { return CBContext != nullptr; }
930
931	/// Special DenseMap key values.
932	///
933	///{
934	static const IRPosition EmptyKey;
935	static const IRPosition TombstoneKey;
936	///}
937
938	/// Conversion into a void * to allow reuse of pointer hashing.
939	operator void *() const { return Enc.getOpaqueValue(); }
940
941	private:
942	/// Private constructor for special values only!
943	explicit IRPosition(void *Ptr, const CallBaseContext *CBContext = nullptr)
944	: CBContext(CBContext) {
945	Enc.setFromOpaqueValue(Ptr);
946	}
947
948	/// IRPosition anchored at \p AnchorVal with kind/argument numbet \p PK.
949	explicit IRPosition(Value &AnchorVal, Kind PK,
950	const CallBaseContext *CBContext = nullptr)
951	: CBContext(CBContext) {
952	switch (PK) {
953	case IRPosition::IRP_INVALID:
954	llvm_unreachable("Cannot create invalid IRP with an anchor value!");
955	break;
956	case IRPosition::IRP_FLOAT:
957	// Special case for floating functions.
958	if (isa<Function>(Val: AnchorVal) || isa<CallBase>(Val: AnchorVal))
959	Enc = {&AnchorVal, ENC_FLOATING_FUNCTION};
960	else
961	Enc = {&AnchorVal, ENC_VALUE};
962	break;
963	case IRPosition::IRP_FUNCTION:
964	case IRPosition::IRP_CALL_SITE:
965	Enc = {&AnchorVal, ENC_VALUE};
966	break;
967	case IRPosition::IRP_RETURNED:
968	case IRPosition::IRP_CALL_SITE_RETURNED:
969	Enc = {&AnchorVal, ENC_RETURNED_VALUE};
970	break;
971	case IRPosition::IRP_ARGUMENT:
972	Enc = {&AnchorVal, ENC_VALUE};
973	break;
974	case IRPosition::IRP_CALL_SITE_ARGUMENT:
975	llvm_unreachable(
976	"Cannot create call site argument IRP with an anchor value!");
977	break;
978	}
979	verify();
980	}
981
982	/// Return the callee argument number of the associated value if it is an
983	/// argument or call site argument. See also `getCalleeArgNo` and
984	/// `getCallSiteArgNo`.
985	int getArgNo(bool CallbackCalleeArgIfApplicable) const {
986	if (CallbackCalleeArgIfApplicable)
987	if (Argument *Arg = getAssociatedArgument())
988	return Arg->getArgNo();
989	switch (getPositionKind()) {
990	case IRPosition::IRP_ARGUMENT:
991	return cast<Argument>(Val: getAsValuePtr())->getArgNo();
992	case IRPosition::IRP_CALL_SITE_ARGUMENT: {
993	Use &U = *getAsUsePtr();
994	return cast<CallBase>(Val: U.getUser())->getArgOperandNo(U: &U);
995	}
996	default:
997	return -1;
998	}
999	}
1000
1001	/// IRPosition for the use \p U. The position kind \p PK needs to be
1002	/// IRP_CALL_SITE_ARGUMENT, the anchor value is the user, the associated value
1003	/// the used value.
1004	explicit IRPosition(Use &U, Kind PK) {
1005	assert(PK == IRP_CALL_SITE_ARGUMENT &&
1006	"Use constructor is for call site arguments only!");
1007	Enc = {&U, ENC_CALL_SITE_ARGUMENT_USE};
1008	verify();
1009	}
1010
1011	/// Verify internal invariants.
1012	void verify();
1013
1014	/// Return the underlying pointer as Value *, valid for all positions but
1015	/// IRP_CALL_SITE_ARGUMENT.
1016	Value *getAsValuePtr() const {
1017	assert(getEncodingBits() != ENC_CALL_SITE_ARGUMENT_USE &&
1018	"Not a value pointer!");
1019	return reinterpret_cast<Value *>(Enc.getPointer());
1020	}
1021
1022	/// Return the underlying pointer as Use *, valid only for
1023	/// IRP_CALL_SITE_ARGUMENT positions.
1024	Use *getAsUsePtr() const {
1025	assert(getEncodingBits() == ENC_CALL_SITE_ARGUMENT_USE &&
1026	"Not a value pointer!");
1027	return reinterpret_cast<Use *>(Enc.getPointer());
1028	}
1029
1030	/// Return true if \p EncodingBits describe a returned or call site returned
1031	/// position.
1032	static bool isReturnPosition(char EncodingBits) {
1033	return EncodingBits == ENC_RETURNED_VALUE;
1034	}
1035
1036	/// Return true if the encoding bits describe a returned or call site returned
1037	/// position.
1038	bool isReturnPosition() const { return isReturnPosition(EncodingBits: getEncodingBits()); }
1039
1040	/// The encoding of the IRPosition is a combination of a pointer and two
1041	/// encoding bits. The values of the encoding bits are defined in the enum
1042	/// below. The pointer is either a Value* (for the first three encoding bit
1043	/// combinations) or Use* (for ENC_CALL_SITE_ARGUMENT_USE).
1044	///
1045	///{
1046	enum {
1047	ENC_VALUE = 0b00,
1048	ENC_RETURNED_VALUE = 0b01,
1049	ENC_FLOATING_FUNCTION = 0b10,
1050	ENC_CALL_SITE_ARGUMENT_USE = 0b11,
1051	};
1052
1053	// Reserve the maximal amount of bits so there is no need to mask out the
1054	// remaining ones. We will not encode anything else in the pointer anyway.
1055	static constexpr int NumEncodingBits =
1056	PointerLikeTypeTraits<void *>::NumLowBitsAvailable;
1057	static_assert(NumEncodingBits >= 2, "At least two bits are required!");
1058
1059	/// The pointer with the encoding bits.
1060	PointerIntPair<void *, NumEncodingBits, char> Enc;
1061	///}
1062
1063	/// Call base context. Used for callsite specific analysis.
1064	const CallBaseContext *CBContext = nullptr;
1065
1066	/// Return the encoding bits.
1067	char getEncodingBits() const { return Enc.getInt(); }
1068	};
1069
1070	/// Helper that allows IRPosition as a key in a DenseMap.
1071	template <> struct DenseMapInfo<IRPosition> {
1072	static inline IRPosition getEmptyKey() { return IRPosition::EmptyKey; }
1073	static inline IRPosition getTombstoneKey() {
1074	return IRPosition::TombstoneKey;
1075	}
1076	static unsigned getHashValue(const IRPosition &IRP) {
1077	return (DenseMapInfo<void *>::getHashValue(PtrVal: IRP) << 4) ^
1078	(DenseMapInfo<Value *>::getHashValue(PtrVal: IRP.getCallBaseContext()));
1079	}
1080
1081	static bool isEqual(const IRPosition &a, const IRPosition &b) {
1082	return a == b;
1083	}
1084	};
1085
1086	/// A visitor class for IR positions.
1087	///
1088	/// Given a position P, the SubsumingPositionIterator allows to visit "subsuming
1089	/// positions" wrt. attributes/information. Thus, if a piece of information
1090	/// holds for a subsuming position, it also holds for the position P.
1091	///
1092	/// The subsuming positions always include the initial position and then,
1093	/// depending on the position kind, additionally the following ones:
1094	/// - for IRP_RETURNED:
1095	/// - the function (IRP_FUNCTION)
1096	/// - for IRP_ARGUMENT:
1097	/// - the function (IRP_FUNCTION)
1098	/// - for IRP_CALL_SITE:
1099	/// - the callee (IRP_FUNCTION), if known
1100	/// - for IRP_CALL_SITE_RETURNED:
1101	/// - the callee (IRP_RETURNED), if known
1102	/// - the call site (IRP_FUNCTION)
1103	/// - the callee (IRP_FUNCTION), if known
1104	/// - for IRP_CALL_SITE_ARGUMENT:
1105	/// - the argument of the callee (IRP_ARGUMENT), if known
1106	/// - the callee (IRP_FUNCTION), if known
1107	/// - the position the call site argument is associated with if it is not
1108	/// anchored to the call site, e.g., if it is an argument then the argument
1109	/// (IRP_ARGUMENT)
1110	class SubsumingPositionIterator {
1111	SmallVector<IRPosition, 4> IRPositions;
1112	using iterator = decltype(IRPositions)::iterator;
1113
1114	public:
1115	SubsumingPositionIterator(const IRPosition &IRP);
1116	iterator begin() { return IRPositions.begin(); }
1117	iterator end() { return IRPositions.end(); }
1118	};
1119
1120	/// Wrapper for FunctionAnalysisManager.
1121	struct AnalysisGetter {
1122	// The client may be running the old pass manager, in which case, we need to
1123	// map the requested Analysis to its equivalent wrapper in the old pass
1124	// manager. The scheme implemented here does not require every Analysis to be
1125	// updated. Only those new analyses that the client cares about in the old
1126	// pass manager need to expose a LegacyWrapper type, and that wrapper should
1127	// support a getResult() method that matches the new Analysis.
1128	//
1129	// We need SFINAE to check for the LegacyWrapper, but function templates don't
1130	// allow partial specialization, which is needed in this case. So instead, we
1131	// use a constexpr bool to perform the SFINAE, and then use this information
1132	// inside the function template.
1133	template <typename, typename = void>
1134	static constexpr bool HasLegacyWrapper = false;
1135
1136	template <typename Analysis>
1137	typename Analysis::Result *getAnalysis(const Function &F,
1138	bool RequestCachedOnly = false) {
1139	if (!LegacyPass && !FAM)
1140	return nullptr;
1141	if (FAM) {
1142	if (CachedOnly || RequestCachedOnly)
1143	return FAM->getCachedResult<Analysis>(const_cast<Function &>(F));
1144	return &FAM->getResult<Analysis>(const_cast<Function &>(F));
1145	}
1146	if constexpr (HasLegacyWrapper<Analysis>) {
1147	if (!CachedOnly && !RequestCachedOnly)
1148	return &LegacyPass
1149	->getAnalysis<typename Analysis::LegacyWrapper>(
1150	const_cast<Function &>(F))
1151	.getResult();
1152	if (auto *P =
1153	LegacyPass
1154	->getAnalysisIfAvailable<typename Analysis::LegacyWrapper>())
1155	return &P->getResult();
1156	}
1157	return nullptr;
1158	}
1159
1160	/// Invalidates the analyses. Valid only when using the new pass manager.
1161	void invalidateAnalyses() {
1162	assert(FAM && "Can only be used from the new PM!");
1163	FAM->clear();
1164	}
1165
1166	AnalysisGetter(FunctionAnalysisManager &FAM, bool CachedOnly = false)
1167	: FAM(&FAM), CachedOnly(CachedOnly) {}
1168	AnalysisGetter(Pass *P, bool CachedOnly = false)
1169	: LegacyPass(P), CachedOnly(CachedOnly) {}
1170	AnalysisGetter() = default;
1171
1172	private:
1173	FunctionAnalysisManager *FAM = nullptr;
1174	Pass *LegacyPass = nullptr;
1175
1176	/// If \p CachedOnly is true, no pass is created, just existing results are
1177	/// used. Also available per request.
1178	bool CachedOnly = false;
1179	};
1180
1181	template <typename Analysis>
1182	constexpr bool AnalysisGetter::HasLegacyWrapper<
1183	Analysis, std::void_t<typename Analysis::LegacyWrapper>> = true;
1184
1185	/// Data structure to hold cached (LLVM-IR) information.
1186	///
1187	/// All attributes are given an InformationCache object at creation time to
1188	/// avoid inspection of the IR by all of them individually. This default
1189	/// InformationCache will hold information required by 'default' attributes,
1190	/// thus the ones deduced when Attributor::identifyDefaultAbstractAttributes(..)
1191	/// is called.
1192	///
1193	/// If custom abstract attributes, registered manually through
1194	/// Attributor::registerAA(...), need more information, especially if it is not
1195	/// reusable, it is advised to inherit from the InformationCache and cast the
1196	/// instance down in the abstract attributes.
1197	struct InformationCache {
1198	InformationCache(const Module &M, AnalysisGetter &AG,
1199	BumpPtrAllocator &Allocator, SetVector<Function *> *CGSCC,
1200	bool UseExplorer = true)
1201	: CGSCC(CGSCC), DL(M.getDataLayout()), Allocator(Allocator), AG(AG),
1202	TargetTriple(M.getTargetTriple()) {
1203	if (UseExplorer)
1204	Explorer = new (Allocator) MustBeExecutedContextExplorer(
1205	/* ExploreInterBlock */ true, /* ExploreCFGForward */ true,
1206	/* ExploreCFGBackward */ true,
1207	/* LIGetter */
1208	[&](const Function &F) { return AG.getAnalysis<LoopAnalysis>(F); },
1209	/* DTGetter */
1210	[&](const Function &F) {
1211	return AG.getAnalysis<DominatorTreeAnalysis>(F);
1212	},
1213	/* PDTGetter */
1214	[&](const Function &F) {
1215	return AG.getAnalysis<PostDominatorTreeAnalysis>(F);
1216	});
1217	}
1218
1219	~InformationCache() {
1220	// The FunctionInfo objects are allocated via a BumpPtrAllocator, we call
1221	// the destructor manually.
1222	for (auto &It : FuncInfoMap)
1223	It.getSecond()->~FunctionInfo();
1224	// Same is true for the instruction exclusions sets.
1225	using AA::InstExclusionSetTy;
1226	for (auto *BES : BESets)
1227	BES->~InstExclusionSetTy();
1228	if (Explorer)
1229	Explorer->~MustBeExecutedContextExplorer();
1230	}
1231
1232	/// Apply \p CB to all uses of \p F. If \p LookThroughConstantExprUses is
1233	/// true, constant expression users are not given to \p CB but their uses are
1234	/// traversed transitively.
1235	template <typename CBTy>
1236	static void foreachUse(Function &F, CBTy CB,
1237	bool LookThroughConstantExprUses = true) {
1238	SmallVector<Use *, 8> Worklist(make_pointer_range(Range: F.uses()));
1239
1240	for (unsigned Idx = 0; Idx < Worklist.size(); ++Idx) {
1241	Use &U = *Worklist[Idx];
1242
1243	// Allow use in constant bitcasts and simply look through them.
1244	if (LookThroughConstantExprUses && isa<ConstantExpr>(Val: U.getUser())) {
1245	for (Use &CEU : cast<ConstantExpr>(Val: U.getUser())->uses())
1246	Worklist.push_back(Elt: &CEU);
1247	continue;
1248	}
1249
1250	CB(U);
1251	}
1252	}
1253
1254	/// The CG-SCC the pass is run on, or nullptr if it is a module pass.
1255	const SetVector<Function *> *const CGSCC = nullptr;
1256
1257	/// A vector type to hold instructions.
1258	using InstructionVectorTy = SmallVector<Instruction *, 8>;
1259
1260	/// A map type from opcodes to instructions with this opcode.
1261	using OpcodeInstMapTy = DenseMap<unsigned, InstructionVectorTy *>;
1262
1263	/// Return the map that relates "interesting" opcodes with all instructions
1264	/// with that opcode in \p F.
1265	OpcodeInstMapTy &getOpcodeInstMapForFunction(const Function &F) {
1266	return getFunctionInfo(F).OpcodeInstMap;
1267	}
1268
1269	/// Return the instructions in \p F that may read or write memory.
1270	InstructionVectorTy &getReadOrWriteInstsForFunction(const Function &F) {
1271	return getFunctionInfo(F).RWInsts;
1272	}
1273
1274	/// Return MustBeExecutedContextExplorer
1275	MustBeExecutedContextExplorer *getMustBeExecutedContextExplorer() {
1276	return Explorer;
1277	}
1278
1279	/// Return TargetLibraryInfo for function \p F.
1280	TargetLibraryInfo *getTargetLibraryInfoForFunction(const Function &F) {
1281	return AG.getAnalysis<TargetLibraryAnalysis>(F);
1282	}
1283
1284	/// Return true if \p Arg is involved in a must-tail call, thus the argument
1285	/// of the caller or callee.
1286	bool isInvolvedInMustTailCall(const Argument &Arg) {
1287	FunctionInfo &FI = getFunctionInfo(F: *Arg.getParent());
1288	return FI.CalledViaMustTail || FI.ContainsMustTailCall;
1289	}
1290
1291	bool isOnlyUsedByAssume(const Instruction &I) const {
1292	return AssumeOnlyValues.contains(key: &I);
1293	}
1294
1295	/// Invalidates the cached analyses. Valid only when using the new pass
1296	/// manager.
1297	void invalidateAnalyses() { AG.invalidateAnalyses(); }
1298
1299	/// Return the analysis result from a pass \p AP for function \p F.
1300	template <typename AP>
1301	typename AP::Result *getAnalysisResultForFunction(const Function &F,
1302	bool CachedOnly = false) {
1303	return AG.getAnalysis<AP>(F, CachedOnly);
1304	}
1305
1306	/// Return datalayout used in the module.
1307	const DataLayout &getDL() { return DL; }
1308
1309	/// Return the map conaining all the knowledge we have from `llvm.assume`s.
1310	const RetainedKnowledgeMap &getKnowledgeMap() const { return KnowledgeMap; }
1311
1312	/// Given \p BES, return a uniqued version.
1313	const AA::InstExclusionSetTy *
1314	getOrCreateUniqueBlockExecutionSet(const AA::InstExclusionSetTy *BES) {
1315	auto It = BESets.find(V: BES);
1316	if (It != BESets.end())
1317	return *It;
1318	auto *UniqueBES = new (Allocator) AA::InstExclusionSetTy(*BES);
1319	bool Success = BESets.insert(V: UniqueBES).second;
1320	(void)Success;
1321	assert(Success && "Expected only new entries to be added");
1322	return UniqueBES;
1323	}
1324
1325	/// Return true if the stack (llvm::Alloca) can be accessed by other threads.
1326	bool stackIsAccessibleByOtherThreads() { return !targetIsGPU(); }
1327
1328	/// Return true if the target is a GPU.
1329	bool targetIsGPU() {
1330	return TargetTriple.isAMDGPU() || TargetTriple.isNVPTX();
1331	}
1332
1333	/// Return all functions that might be called indirectly, only valid for
1334	/// closed world modules (see isClosedWorldModule).
1335	const ArrayRef<Function *>
1336	getIndirectlyCallableFunctions(Attributor &A) const;
1337
1338	private:
1339	struct FunctionInfo {
1340	~FunctionInfo();
1341
1342	/// A nested map that remembers all instructions in a function with a
1343	/// certain instruction opcode (Instruction::getOpcode()).
1344	OpcodeInstMapTy OpcodeInstMap;
1345
1346	/// A map from functions to their instructions that may read or write
1347	/// memory.
1348	InstructionVectorTy RWInsts;
1349
1350	/// Function is called by a `musttail` call.
1351	bool CalledViaMustTail;
1352
1353	/// Function contains a `musttail` call.
1354	bool ContainsMustTailCall;
1355	};
1356
1357	/// A map type from functions to informatio about it.
1358	DenseMap<const Function *, FunctionInfo *> FuncInfoMap;
1359
1360	/// Return information about the function \p F, potentially by creating it.
1361	FunctionInfo &getFunctionInfo(const Function &F) {
1362	FunctionInfo *&FI = FuncInfoMap[&F];
1363	if (!FI) {
1364	FI = new (Allocator) FunctionInfo();
1365	initializeInformationCache(F, FI&: *FI);
1366	}
1367	return *FI;
1368	}
1369
1370	/// Vector of functions that might be callable indirectly, i.a., via a
1371	/// function pointer.
1372	SmallVector<Function *> IndirectlyCallableFunctions;
1373
1374	/// Initialize the function information cache \p FI for the function \p F.
1375	///
1376	/// This method needs to be called for all function that might be looked at
1377	/// through the information cache interface *prior* to looking at them.
1378	void initializeInformationCache(const Function &F, FunctionInfo &FI);
1379
1380	/// The datalayout used in the module.
1381	const DataLayout &DL;
1382
1383	/// The allocator used to allocate memory, e.g. for `FunctionInfo`s.
1384	BumpPtrAllocator &Allocator;
1385
1386	/// MustBeExecutedContextExplorer
1387	MustBeExecutedContextExplorer *Explorer = nullptr;
1388
1389	/// A map with knowledge retained in `llvm.assume` instructions.
1390	RetainedKnowledgeMap KnowledgeMap;
1391
1392	/// A container for all instructions that are only used by `llvm.assume`.
1393	SetVector<const Instruction *> AssumeOnlyValues;
1394
1395	/// Cache for block sets to allow reuse.
1396	DenseSet<const AA::InstExclusionSetTy *> BESets;
1397
1398	/// Getters for analysis.
1399	AnalysisGetter &AG;
1400
1401	/// Set of inlineable functions
1402	SmallPtrSet<const Function *, 8> InlineableFunctions;
1403
1404	/// The triple describing the target machine.
1405	Triple TargetTriple;
1406
1407	/// Give the Attributor access to the members so
1408	/// Attributor::identifyDefaultAbstractAttributes(...) can initialize them.
1409	friend struct Attributor;
1410	};
1411
1412	/// Configuration for the Attributor.
1413	struct AttributorConfig {
1414
1415	AttributorConfig(CallGraphUpdater &CGUpdater) : CGUpdater(CGUpdater) {}
1416
1417	/// Is the user of the Attributor a module pass or not. This determines what
1418	/// IR we can look at and modify. If it is a module pass we might deduce facts
1419	/// outside the initial function set and modify functions outside that set,
1420	/// but only as part of the optimization of the functions in the initial
1421	/// function set. For CGSCC passes we can look at the IR of the module slice
1422	/// but never run any deduction, or perform any modification, outside the
1423	/// initial function set (which we assume is the SCC).
1424	bool IsModulePass = true;
1425
1426	/// Flag to determine if we can delete functions or keep dead ones around.
1427	bool DeleteFns = true;
1428
1429	/// Flag to determine if we rewrite function signatures.
1430	bool RewriteSignatures = true;
1431
1432	/// Flag to determine if we want to initialize all default AAs for an internal
1433	/// function marked live. See also: InitializationCallback>
1434	bool DefaultInitializeLiveInternals = true;
1435
1436	/// Flag to determine if we should skip all liveness checks early on.
1437	bool UseLiveness = true;
1438
1439	/// Flag to indicate if the entire world is contained in this module, that
1440	/// is, no outside functions exist.
1441	bool IsClosedWorldModule = false;
1442
1443	/// Callback function to be invoked on internal functions marked live.
1444	std::function<void(Attributor &A, const Function &F)> InitializationCallback =
1445	nullptr;
1446
1447	/// Callback function to determine if an indirect call targets should be made
1448	/// direct call targets (with an if-cascade).
1449	std::function<bool(Attributor &A, const AbstractAttribute &AA, CallBase &CB,
1450	Function &AssummedCallee)>
1451	IndirectCalleeSpecializationCallback = nullptr;
1452
1453	/// Helper to update an underlying call graph and to delete functions.
1454	CallGraphUpdater &CGUpdater;
1455
1456	/// If not null, a set limiting the attribute opportunities.
1457	DenseSet<const char *> *Allowed = nullptr;
1458
1459	/// Maximum number of iterations to run until fixpoint.
1460	std::optional<unsigned> MaxFixpointIterations;
1461
1462	/// A callback function that returns an ORE object from a Function pointer.
1463	///{
1464	using OptimizationRemarkGetter =
1465	function_ref<OptimizationRemarkEmitter &(Function *)>;
1466	OptimizationRemarkGetter OREGetter = nullptr;
1467	///}
1468
1469	/// The name of the pass running the attributor, used to emit remarks.
1470	const char *PassName = nullptr;
1471
1472	using IPOAmendableCBTy = function_ref<bool(const Function &F)>;
1473	IPOAmendableCBTy IPOAmendableCB;
1474	};
1475
1476	/// A debug counter to limit the number of AAs created.
1477	DEBUG_COUNTER(NumAbstractAttributes, "num-abstract-attributes",
1478	"How many AAs should be initialized");
1479
1480	/// The fixpoint analysis framework that orchestrates the attribute deduction.
1481	///
1482	/// The Attributor provides a general abstract analysis framework (guided
1483	/// fixpoint iteration) as well as helper functions for the deduction of
1484	/// (LLVM-IR) attributes. However, also other code properties can be deduced,
1485	/// propagated, and ultimately manifested through the Attributor framework. This
1486	/// is particularly useful if these properties interact with attributes and a
1487	/// co-scheduled deduction allows to improve the solution. Even if not, thus if
1488	/// attributes/properties are completely isolated, they should use the
1489	/// Attributor framework to reduce the number of fixpoint iteration frameworks
1490	/// in the code base. Note that the Attributor design makes sure that isolated
1491	/// attributes are not impacted, in any way, by others derived at the same time
1492	/// if there is no cross-reasoning performed.
1493	///
1494	/// The public facing interface of the Attributor is kept simple and basically
1495	/// allows abstract attributes to one thing, query abstract attributes
1496	/// in-flight. There are two reasons to do this:
1497	/// a) The optimistic state of one abstract attribute can justify an
1498	/// optimistic state of another, allowing to framework to end up with an
1499	/// optimistic (=best possible) fixpoint instead of one based solely on
1500	/// information in the IR.
1501	/// b) This avoids reimplementing various kinds of lookups, e.g., to check
1502	/// for existing IR attributes, in favor of a single lookups interface
1503	/// provided by an abstract attribute subclass.
1504	///
1505	/// NOTE: The mechanics of adding a new "concrete" abstract attribute are
1506	/// described in the file comment.
1507	struct Attributor {
1508
1509	/// Constructor
1510	///
1511	/// \param Functions The set of functions we are deriving attributes for.
1512	/// \param InfoCache Cache to hold various information accessible for
1513	/// the abstract attributes.
1514	/// \param Configuration The Attributor configuration which determines what
1515	/// generic features to use.
1516	Attributor(SetVector<Function *> &Functions, InformationCache &InfoCache,
1517	AttributorConfig Configuration);
1518
1519	~Attributor();
1520
1521	/// Run the analyses until a fixpoint is reached or enforced (timeout).
1522	///
1523	/// The attributes registered with this Attributor can be used after as long
1524	/// as the Attributor is not destroyed (it owns the attributes now).
1525	///
1526	/// \Returns CHANGED if the IR was changed, otherwise UNCHANGED.
1527	ChangeStatus run();
1528
1529	/// Lookup an abstract attribute of type \p AAType at position \p IRP. While
1530	/// no abstract attribute is found equivalent positions are checked, see
1531	/// SubsumingPositionIterator. Thus, the returned abstract attribute
1532	/// might be anchored at a different position, e.g., the callee if \p IRP is a
1533	/// call base.
1534	///
1535	/// This method is the only (supported) way an abstract attribute can retrieve
1536	/// information from another abstract attribute. As an example, take an
1537	/// abstract attribute that determines the memory access behavior for a
1538	/// argument (readnone, readonly, ...). It should use `getAAFor` to get the
1539	/// most optimistic information for other abstract attributes in-flight, e.g.
1540	/// the one reasoning about the "captured" state for the argument or the one
1541	/// reasoning on the memory access behavior of the function as a whole.
1542	///
1543	/// If the DepClass enum is set to `DepClassTy::None` the dependence from
1544	/// \p QueryingAA to the return abstract attribute is not automatically
1545	/// recorded. This should only be used if the caller will record the
1546	/// dependence explicitly if necessary, thus if it the returned abstract
1547	/// attribute is used for reasoning. To record the dependences explicitly use
1548	/// the `Attributor::recordDependence` method.
1549	template <typename AAType>
1550	const AAType *getAAFor(const AbstractAttribute &QueryingAA,
1551	const IRPosition &IRP, DepClassTy DepClass) {
1552	return getOrCreateAAFor<AAType>(IRP, &QueryingAA, DepClass,
1553	/* ForceUpdate */ false);
1554	}
1555
1556	/// The version of getAAFor that allows to omit a querying abstract
1557	/// attribute. Using this after Attributor started running is restricted to
1558	/// only the Attributor itself. Initial seeding of AAs can be done via this
1559	/// function.
1560	/// NOTE: ForceUpdate is ignored in any stage other than the update stage.
1561	template <typename AAType>
1562	const AAType *getOrCreateAAFor(IRPosition IRP,
1563	const AbstractAttribute *QueryingAA,
1564	DepClassTy DepClass, bool ForceUpdate = false,
1565	bool UpdateAfterInit = true) {
1566	if (!shouldPropagateCallBaseContext(IRP))
1567	IRP = IRP.stripCallBaseContext();
1568
1569	if (AAType *AAPtr = lookupAAFor<AAType>(IRP, QueryingAA, DepClass,
1570	/* AllowInvalidState */ true)) {
1571	if (ForceUpdate && Phase == AttributorPhase::UPDATE)
1572	updateAA(AA&: *AAPtr);
1573	return AAPtr;
1574	}
1575
1576	bool ShouldUpdateAA;
1577	if (!shouldInitialize<AAType>(IRP, ShouldUpdateAA))
1578	return nullptr;
1579
1580	if (!DebugCounter::shouldExecute(CounterName: NumAbstractAttributes))
1581	return nullptr;
1582
1583	// No matching attribute found, create one.
1584	// Use the static create method.
1585	auto &AA = AAType::createForPosition(IRP, *this);
1586
1587	// Always register a new attribute to make sure we clean up the allocated
1588	// memory properly.
1589	registerAA(AA);
1590
1591	// If we are currenty seeding attributes, enforce seeding rules.
1592	if (Phase == AttributorPhase::SEEDING && !shouldSeedAttribute(AA)) {
1593	AA.getState().indicatePessimisticFixpoint();
1594	return &AA;
1595	}
1596
1597	// Bootstrap the new attribute with an initial update to propagate
1598	// information, e.g., function -> call site.
1599	{
1600	TimeTraceScope TimeScope("initialize", [&]() {
1601	return AA.getName() +
1602	std::to_string(AA.getIRPosition().getPositionKind());
1603	});
1604	++InitializationChainLength;
1605	AA.initialize(*this);
1606	--InitializationChainLength;
1607	}
1608
1609	if (!ShouldUpdateAA) {
1610	AA.getState().indicatePessimisticFixpoint();
1611	return &AA;
1612	}
1613
1614	// Allow seeded attributes to declare dependencies.
1615	// Remember the seeding state.
1616	if (UpdateAfterInit) {
1617	AttributorPhase OldPhase = Phase;
1618	Phase = AttributorPhase::UPDATE;
1619
1620	updateAA(AA);
1621
1622	Phase = OldPhase;
1623	}
1624
1625	if (QueryingAA && AA.getState().isValidState())
1626	recordDependence(FromAA: AA, ToAA: const_cast<AbstractAttribute &>(*QueryingAA),
1627	DepClass);
1628	return &AA;
1629	}
1630
1631	template <typename AAType>
1632	const AAType *getOrCreateAAFor(const IRPosition &IRP) {
1633	return getOrCreateAAFor<AAType>(IRP, /* QueryingAA */ nullptr,
1634	DepClassTy::NONE);
1635	}
1636
1637	/// Return the attribute of \p AAType for \p IRP if existing and valid. This
1638	/// also allows non-AA users lookup.
1639	template <typename AAType>
1640	AAType *lookupAAFor(const IRPosition &IRP,
1641	const AbstractAttribute *QueryingAA = nullptr,
1642	DepClassTy DepClass = DepClassTy::OPTIONAL,
1643	bool AllowInvalidState = false) {
1644	static_assert(std::is_base_of<AbstractAttribute, AAType>::value,
1645	"Cannot query an attribute with a type not derived from "
1646	"'AbstractAttribute'!");
1647	// Lookup the abstract attribute of type AAType. If found, return it after
1648	// registering a dependence of QueryingAA on the one returned attribute.
1649	AbstractAttribute *AAPtr = AAMap.lookup(Val: {&AAType::ID, IRP});
1650	if (!AAPtr)
1651	return nullptr;
1652
1653	AAType *AA = static_cast<AAType *>(AAPtr);
1654
1655	// Do not register a dependence on an attribute with an invalid state.
1656	if (DepClass != DepClassTy::NONE && QueryingAA &&
1657	AA->getState().isValidState())
1658	recordDependence(FromAA: *AA, ToAA: const_cast<AbstractAttribute &>(*QueryingAA),
1659	DepClass);
1660
1661	// Return nullptr if this attribute has an invalid state.
1662	if (!AllowInvalidState && !AA->getState().isValidState())
1663	return nullptr;
1664	return AA;
1665	}
1666
1667	/// Allows a query AA to request an update if a new query was received.
1668	void registerForUpdate(AbstractAttribute &AA);
1669
1670	/// Explicitly record a dependence from \p FromAA to \p ToAA, that is if
1671	/// \p FromAA changes \p ToAA should be updated as well.
1672	///
1673	/// This method should be used in conjunction with the `getAAFor` method and
1674	/// with the DepClass enum passed to the method set to None. This can
1675	/// be beneficial to avoid false dependences but it requires the users of
1676	/// `getAAFor` to explicitly record true dependences through this method.
1677	/// The \p DepClass flag indicates if the dependence is striclty necessary.
1678	/// That means for required dependences, if \p FromAA changes to an invalid
1679	/// state, \p ToAA can be moved to a pessimistic fixpoint because it required
1680	/// information from \p FromAA but none are available anymore.
1681	void recordDependence(const AbstractAttribute &FromAA,
1682	const AbstractAttribute &ToAA, DepClassTy DepClass);
1683
1684	/// Introduce a new abstract attribute into the fixpoint analysis.
1685	///
1686	/// Note that ownership of the attribute is given to the Attributor. It will
1687	/// invoke delete for the Attributor on destruction of the Attributor.
1688	///
1689	/// Attributes are identified by their IR position (AAType::getIRPosition())
1690	/// and the address of their static member (see AAType::ID).
1691	template <typename AAType> AAType &registerAA(AAType &AA) {
1692	static_assert(std::is_base_of<AbstractAttribute, AAType>::value,
1693	"Cannot register an attribute with a type not derived from "
1694	"'AbstractAttribute'!");
1695	// Put the attribute in the lookup map structure and the container we use to
1696	// keep track of all attributes.
1697	const IRPosition &IRP = AA.getIRPosition();
1698	AbstractAttribute *&AAPtr = AAMap[{&AAType::ID, IRP}];
1699
1700	assert(!AAPtr && "Attribute already in map!");
1701	AAPtr = &AA;
1702
1703	// Register AA with the synthetic root only before the manifest stage.
1704	if (Phase == AttributorPhase::SEEDING || Phase == AttributorPhase::UPDATE)
1705	DG.SyntheticRoot.Deps.insert(
1706	X: AADepGraphNode::DepTy(&AA, unsigned(DepClassTy::REQUIRED)));
1707
1708	return AA;
1709	}
1710
1711	/// Return the internal information cache.
1712	InformationCache &getInfoCache() { return InfoCache; }
1713
1714	/// Return true if this is a module pass, false otherwise.
1715	bool isModulePass() const { return Configuration.IsModulePass; }
1716
1717	/// Return true if we should specialize the call site \b CB for the potential
1718	/// callee \p Fn.
1719	bool shouldSpecializeCallSiteForCallee(const AbstractAttribute &AA,
1720	CallBase &CB, Function &Callee) {
1721	return Configuration.IndirectCalleeSpecializationCallback
1722	? Configuration.IndirectCalleeSpecializationCallback(*this, AA,
1723	CB, Callee)
1724	: true;
1725	}
1726
1727	/// Return true if the module contains the whole world, thus, no outside
1728	/// functions exist.
1729	bool isClosedWorldModule() const;
1730
1731	/// Return true if we derive attributes for \p Fn
1732	bool isRunOn(Function &Fn) const { return isRunOn(Fn: &Fn); }
1733	bool isRunOn(Function *Fn) const {
1734	return Functions.empty() || Functions.count(key: Fn);
1735	}
1736
1737	template <typename AAType> bool shouldUpdateAA(const IRPosition &IRP) {
1738	// If this is queried in the manifest stage, we force the AA to indicate
1739	// pessimistic fixpoint immediately.
1740	if (Phase == AttributorPhase::MANIFEST || Phase == AttributorPhase::CLEANUP)
1741	return false;
1742
1743	Function *AssociatedFn = IRP.getAssociatedFunction();
1744
1745	if (IRP.isAnyCallSitePosition()) {
1746	// Check if we require a callee but there is none.
1747	if (!AssociatedFn && AAType::requiresCalleeForCallBase())
1748	return false;
1749
1750	// Check if we require non-asm but it is inline asm.
1751	if (AAType::requiresNonAsmForCallBase() &&
1752	cast<CallBase>(Val&: IRP.getAnchorValue()).isInlineAsm())
1753	return false;
1754	}
1755
1756	// Check if we require a calles but we can't see all.
1757	if (AAType::requiresCallersForArgOrFunction())
1758	if (IRP.getPositionKind() == IRPosition::IRP_FUNCTION ||
1759	IRP.getPositionKind() == IRPosition::IRP_ARGUMENT)
1760	if (!AssociatedFn->hasLocalLinkage())
1761	return false;
1762
1763	if (!AAType::isValidIRPositionForUpdate(*this, IRP))
1764	return false;
1765
1766	// We update only AAs associated with functions in the Functions set or
1767	// call sites of them.
1768	return (!AssociatedFn || isModulePass() || isRunOn(Fn: AssociatedFn) ||
1769	isRunOn(Fn: IRP.getAnchorScope()));
1770	}
1771
1772	template <typename AAType>
1773	bool shouldInitialize(const IRPosition &IRP, bool &ShouldUpdateAA) {
1774	if (!AAType::isValidIRPositionForInit(*this, IRP))
1775	return false;
1776
1777	if (Configuration.Allowed && !Configuration.Allowed->count(V: &AAType::ID))
1778	return false;
1779
1780	// For now we skip anything in naked and optnone functions.
1781	const Function *AnchorFn = IRP.getAnchorScope();
1782	if (AnchorFn && (AnchorFn->hasFnAttribute(Attribute::Naked) ||
1783	AnchorFn->hasFnAttribute(Attribute::OptimizeNone)))
1784	return false;
1785
1786	// Avoid too many nested initializations to prevent a stack overflow.
1787	if (InitializationChainLength > MaxInitializationChainLength)
1788	return false;
1789
1790	ShouldUpdateAA = shouldUpdateAA<AAType>(IRP);
1791
1792	return !AAType::hasTrivialInitializer() || ShouldUpdateAA;
1793	}
1794
1795	/// Determine opportunities to derive 'default' attributes in \p F and create
1796	/// abstract attribute objects for them.
1797	///
1798	/// \param F The function that is checked for attribute opportunities.
1799	///
1800	/// Note that abstract attribute instances are generally created even if the
1801	/// IR already contains the information they would deduce. The most important
1802	/// reason for this is the single interface, the one of the abstract attribute
1803	/// instance, which can be queried without the need to look at the IR in
1804	/// various places.
1805	void identifyDefaultAbstractAttributes(Function &F);
1806
1807	/// Determine whether the function \p F is IPO amendable
1808	///
1809	/// If a function is exactly defined or it has alwaysinline attribute
1810	/// and is viable to be inlined, we say it is IPO amendable
1811	bool isFunctionIPOAmendable(const Function &F) {
1812	return F.hasExactDefinition() || InfoCache.InlineableFunctions.count(Ptr: &F) ||
1813	(Configuration.IPOAmendableCB && Configuration.IPOAmendableCB(F));
1814	}
1815
1816	/// Mark the internal function \p F as live.
1817	///
1818	/// This will trigger the identification and initialization of attributes for
1819	/// \p F.
1820	void markLiveInternalFunction(const Function &F) {
1821	assert(F.hasLocalLinkage() &&
1822	"Only local linkage is assumed dead initially.");
1823
1824	if (Configuration.DefaultInitializeLiveInternals)
1825	identifyDefaultAbstractAttributes(F&: const_cast<Function &>(F));
1826	if (Configuration.InitializationCallback)
1827	Configuration.InitializationCallback(*this, F);
1828	}
1829
1830	/// Helper function to remove callsite.
1831	void removeCallSite(CallInst *CI) {
1832	if (!CI)
1833	return;
1834
1835	Configuration.CGUpdater.removeCallSite(CS&: *CI);
1836	}
1837
1838	/// Record that \p U is to be replaces with \p NV after information was
1839	/// manifested. This also triggers deletion of trivially dead istructions.
1840	bool changeUseAfterManifest(Use &U, Value &NV) {
1841	Value *&V = ToBeChangedUses[&U];
1842	if (V && (V->stripPointerCasts() == NV.stripPointerCasts() ||
1843	isa_and_nonnull<UndefValue>(Val: V)))
1844	return false;
1845	assert((!V || V == &NV || isa<UndefValue>(NV)) &&
1846	"Use was registered twice for replacement with different values!");
1847	V = &NV;
1848	return true;
1849	}
1850
1851	/// Helper function to replace all uses associated with \p IRP with \p NV.
1852	/// Return true if there is any change. The flag \p ChangeDroppable indicates
1853	/// if dropppable uses should be changed too.
1854	bool changeAfterManifest(const IRPosition IRP, Value &NV,
1855	bool ChangeDroppable = true) {
1856	if (IRP.getPositionKind() == IRPosition::IRP_CALL_SITE_ARGUMENT) {
1857	auto *CB = cast<CallBase>(Val: IRP.getCtxI());
1858	return changeUseAfterManifest(
1859	U&: CB->getArgOperandUse(i: IRP.getCallSiteArgNo()), NV);
1860	}
1861	Value &V = IRP.getAssociatedValue();
1862	auto &Entry = ToBeChangedValues[&V];
1863	Value *CurNV = get<0>(Pair: Entry);
1864	if (CurNV && (CurNV->stripPointerCasts() == NV.stripPointerCasts() ||
1865	isa<UndefValue>(Val: CurNV)))
1866	return false;
1867	assert((!CurNV || CurNV == &NV || isa<UndefValue>(NV)) &&
1868	"Value replacement was registered twice with different values!");
1869	Entry = {&NV, ChangeDroppable};
1870	return true;
1871	}
1872
1873	/// Record that \p I is to be replaced with `unreachable` after information
1874	/// was manifested.
1875	void changeToUnreachableAfterManifest(Instruction *I) {
1876	ToBeChangedToUnreachableInsts.insert(X: I);
1877	}
1878
1879	/// Record that \p II has at least one dead successor block. This information
1880	/// is used, e.g., to replace \p II with a call, after information was
1881	/// manifested.
1882	void registerInvokeWithDeadSuccessor(InvokeInst &II) {
1883	InvokeWithDeadSuccessor.insert(X: &II);
1884	}
1885
1886	/// Record that \p I is deleted after information was manifested. This also
1887	/// triggers deletion of trivially dead istructions.
1888	void deleteAfterManifest(Instruction &I) { ToBeDeletedInsts.insert(X: &I); }
1889
1890	/// Record that \p BB is deleted after information was manifested. This also
1891	/// triggers deletion of trivially dead istructions.
1892	void deleteAfterManifest(BasicBlock &BB) { ToBeDeletedBlocks.insert(X: &BB); }
1893
1894	// Record that \p BB is added during the manifest of an AA. Added basic blocks
1895	// are preserved in the IR.
1896	void registerManifestAddedBasicBlock(BasicBlock &BB) {
1897	ManifestAddedBlocks.insert(Ptr: &BB);
1898	}
1899
1900	/// Record that \p F is deleted after information was manifested.
1901	void deleteAfterManifest(Function &F) {
1902	if (Configuration.DeleteFns)
1903	ToBeDeletedFunctions.insert(X: &F);
1904	}
1905
1906	/// Return the attributes of kind \p AK existing in the IR as operand bundles
1907	/// of an llvm.assume.
1908	bool getAttrsFromAssumes(const IRPosition &IRP, Attribute::AttrKind AK,
1909	SmallVectorImpl<Attribute> &Attrs);
1910
1911	/// Return true if any kind in \p AKs existing in the IR at a position that
1912	/// will affect this one. See also getAttrs(...).
1913	/// \param IgnoreSubsumingPositions Flag to determine if subsuming positions,
1914	/// e.g., the function position if this is an
1915	/// argument position, should be ignored.
1916	bool hasAttr(const IRPosition &IRP, ArrayRef<Attribute::AttrKind> AKs,
1917	bool IgnoreSubsumingPositions = false,
1918	Attribute::AttrKind ImpliedAttributeKind = Attribute::None);
1919
1920	/// Return the attributes of any kind in \p AKs existing in the IR at a
1921	/// position that will affect this one. While each position can only have a
1922	/// single attribute of any kind in \p AKs, there are "subsuming" positions
1923	/// that could have an attribute as well. This method returns all attributes
1924	/// found in \p Attrs.
1925	/// \param IgnoreSubsumingPositions Flag to determine if subsuming positions,
1926	/// e.g., the function position if this is an
1927	/// argument position, should be ignored.
1928	void getAttrs(const IRPosition &IRP, ArrayRef<Attribute::AttrKind> AKs,
1929	SmallVectorImpl<Attribute> &Attrs,
1930	bool IgnoreSubsumingPositions = false);
1931
1932	/// Remove all \p AttrKinds attached to \p IRP.
1933	ChangeStatus removeAttrs(const IRPosition &IRP,
1934	ArrayRef<Attribute::AttrKind> AttrKinds);
1935	ChangeStatus removeAttrs(const IRPosition &IRP, ArrayRef<StringRef> Attrs);
1936
1937	/// Attach \p DeducedAttrs to \p IRP, if \p ForceReplace is set we do this
1938	/// even if the same attribute kind was already present.
1939	ChangeStatus manifestAttrs(const IRPosition &IRP,
1940	ArrayRef<Attribute> DeducedAttrs,
1941	bool ForceReplace = false);
1942
1943	private:
1944	/// Helper to check \p Attrs for \p AK, if not found, check if \p
1945	/// AAType::isImpliedByIR is true, and if not, create AAType for \p IRP.
1946	template <Attribute::AttrKind AK, typename AAType>
1947	void checkAndQueryIRAttr(const IRPosition &IRP, AttributeSet Attrs);
1948
1949	/// Helper to apply \p CB on all attributes of type \p AttrDescs of \p IRP.
1950	template <typename DescTy>
1951	ChangeStatus updateAttrMap(const IRPosition &IRP, ArrayRef<DescTy> AttrDescs,
1952	function_ref<bool(const DescTy &, AttributeSet,
1953	AttributeMask &, AttrBuilder &)>
1954	CB);
1955
1956	/// Mapping from functions/call sites to their attributes.
1957	DenseMap<Value *, AttributeList> AttrsMap;
1958
1959	public:
1960	/// If \p IRP is assumed to be a constant, return it, if it is unclear yet,
1961	/// return std::nullopt, otherwise return `nullptr`.
1962	std::optional<Constant *> getAssumedConstant(const IRPosition &IRP,
1963	const AbstractAttribute &AA,
1964	bool &UsedAssumedInformation);
1965	std::optional<Constant *> getAssumedConstant(const Value &V,
1966	const AbstractAttribute &AA,
1967	bool &UsedAssumedInformation) {
1968	return getAssumedConstant(IRP: IRPosition::value(V), AA, UsedAssumedInformation);
1969	}
1970
1971	/// If \p V is assumed simplified, return it, if it is unclear yet,
1972	/// return std::nullopt, otherwise return `nullptr`.
1973	std::optional<Value *> getAssumedSimplified(const IRPosition &IRP,
1974	const AbstractAttribute &AA,
1975	bool &UsedAssumedInformation,
1976	AA::ValueScope S) {
1977	return getAssumedSimplified(V: IRP, AA: &AA, UsedAssumedInformation, S);
1978	}
1979	std::optional<Value *> getAssumedSimplified(const Value &V,
1980	const AbstractAttribute &AA,
1981	bool &UsedAssumedInformation,
1982	AA::ValueScope S) {
1983	return getAssumedSimplified(IRP: IRPosition::value(V), AA,
1984	UsedAssumedInformation, S);
1985	}
1986
1987	/// If \p V is assumed simplified, return it, if it is unclear yet,
1988	/// return std::nullopt, otherwise return `nullptr`. Same as the public
1989	/// version except that it can be used without recording dependences on any \p
1990	/// AA.
1991	std::optional<Value *> getAssumedSimplified(const IRPosition &V,
1992	const AbstractAttribute *AA,
1993	bool &UsedAssumedInformation,
1994	AA::ValueScope S);
1995
1996	/// Try to simplify \p IRP and in the scope \p S. If successful, true is
1997	/// returned and all potential values \p IRP can take are put into \p Values.
1998	/// If the result in \p Values contains select or PHI instructions it means
1999	/// those could not be simplified to a single value. Recursive calls with
2000	/// these instructions will yield their respective potential values. If false
2001	/// is returned no other information is valid.
2002	bool getAssumedSimplifiedValues(const IRPosition &IRP,
2003	const AbstractAttribute *AA,
2004	SmallVectorImpl<AA::ValueAndContext> &Values,
2005	AA::ValueScope S,
2006	bool &UsedAssumedInformation,
2007	bool RecurseForSelectAndPHI = true);
2008
2009	/// Register \p CB as a simplification callback.
2010	/// `Attributor::getAssumedSimplified` will use these callbacks before
2011	/// we it will ask `AAValueSimplify`. It is important to ensure this
2012	/// is called before `identifyDefaultAbstractAttributes`, assuming the
2013	/// latter is called at all.
2014	using SimplifictionCallbackTy = std::function<std::optional<Value *>(
2015	const IRPosition &, const AbstractAttribute *, bool &)>;
2016	void registerSimplificationCallback(const IRPosition &IRP,
2017	const SimplifictionCallbackTy &CB) {
2018	SimplificationCallbacks[IRP].emplace_back(Args: CB);
2019	}
2020
2021	/// Return true if there is a simplification callback for \p IRP.
2022	bool hasSimplificationCallback(const IRPosition &IRP) {
2023	return SimplificationCallbacks.count(Val: IRP);
2024	}
2025
2026	/// Register \p CB as a simplification callback.
2027	/// Similar to \p registerSimplificationCallback, the call back will be called
2028	/// first when we simplify a global variable \p GV.
2029	using GlobalVariableSimplifictionCallbackTy =
2030	std::function<std::optional<Constant *>(
2031	const GlobalVariable &, const AbstractAttribute *, bool &)>;
2032	void registerGlobalVariableSimplificationCallback(
2033	const GlobalVariable &GV,
2034	const GlobalVariableSimplifictionCallbackTy &CB) {
2035	GlobalVariableSimplificationCallbacks[&GV].emplace_back(Args: CB);
2036	}
2037
2038	/// Return true if there is a simplification callback for \p GV.
2039	bool hasGlobalVariableSimplificationCallback(const GlobalVariable &GV) {
2040	return GlobalVariableSimplificationCallbacks.count(Val: &GV);
2041	}
2042
2043	/// Return \p std::nullopt if there is no call back registered for \p GV or
2044	/// the call back is still not sure if \p GV can be simplified. Return \p
2045	/// nullptr if \p GV can't be simplified.
2046	std::optional<Constant *>
2047	getAssumedInitializerFromCallBack(const GlobalVariable &GV,
2048	const AbstractAttribute *AA,
2049	bool &UsedAssumedInformation) {
2050	assert(GlobalVariableSimplificationCallbacks.contains(&GV));
2051	for (auto &CB : GlobalVariableSimplificationCallbacks.lookup(Val: &GV)) {
2052	auto SimplifiedGV = CB(GV, AA, UsedAssumedInformation);
2053	// For now we assume the call back will not return a std::nullopt.
2054	assert(SimplifiedGV.has_value() && "SimplifiedGV has not value");
2055	return *SimplifiedGV;
2056	}
2057	llvm_unreachable("there must be a callback registered");
2058	}
2059
2060	using VirtualUseCallbackTy =
2061	std::function<bool(Attributor &, const AbstractAttribute *)>;
2062	void registerVirtualUseCallback(const Value &V,
2063	const VirtualUseCallbackTy &CB) {
2064	VirtualUseCallbacks[&V].emplace_back(Args: CB);
2065	}
2066
2067	private:
2068	/// The vector with all simplification callbacks registered by outside AAs.
2069	DenseMap<IRPosition, SmallVector<SimplifictionCallbackTy, 1>>
2070	SimplificationCallbacks;
2071
2072	/// The vector with all simplification callbacks for global variables
2073	/// registered by outside AAs.
2074	DenseMap<const GlobalVariable *,
2075	SmallVector<GlobalVariableSimplifictionCallbackTy, 1>>
2076	GlobalVariableSimplificationCallbacks;
2077
2078	DenseMap<const Value *, SmallVector<VirtualUseCallbackTy, 1>>
2079	VirtualUseCallbacks;
2080
2081	public:
2082	/// Translate \p V from the callee context into the call site context.
2083	std::optional<Value *>
2084	translateArgumentToCallSiteContent(std::optional<Value *> V, CallBase &CB,
2085	const AbstractAttribute &AA,
2086	bool &UsedAssumedInformation);
2087
2088	/// Return true if \p AA (or its context instruction) is assumed dead.
2089	///
2090	/// If \p LivenessAA is not provided it is queried.
2091	bool isAssumedDead(const AbstractAttribute &AA, const AAIsDead *LivenessAA,
2092	bool &UsedAssumedInformation,
2093	bool CheckBBLivenessOnly = false,
2094	DepClassTy DepClass = DepClassTy::OPTIONAL);
2095
2096	/// Return true if \p I is assumed dead.
2097	///
2098	/// If \p LivenessAA is not provided it is queried.
2099	bool isAssumedDead(const Instruction &I, const AbstractAttribute *QueryingAA,
2100	const AAIsDead *LivenessAA, bool &UsedAssumedInformation,
2101	bool CheckBBLivenessOnly = false,
2102	DepClassTy DepClass = DepClassTy::OPTIONAL,
2103	bool CheckForDeadStore = false);
2104
2105	/// Return true if \p U is assumed dead.
2106	///
2107	/// If \p FnLivenessAA is not provided it is queried.
2108	bool isAssumedDead(const Use &U, const AbstractAttribute *QueryingAA,
2109	const AAIsDead *FnLivenessAA, bool &UsedAssumedInformation,
2110	bool CheckBBLivenessOnly = false,
2111	DepClassTy DepClass = DepClassTy::OPTIONAL);
2112
2113	/// Return true if \p IRP is assumed dead.
2114	///
2115	/// If \p FnLivenessAA is not provided it is queried.
2116	bool isAssumedDead(const IRPosition &IRP, const AbstractAttribute *QueryingAA,
2117	const AAIsDead *FnLivenessAA, bool &UsedAssumedInformation,
2118	bool CheckBBLivenessOnly = false,
2119	DepClassTy DepClass = DepClassTy::OPTIONAL);
2120
2121	/// Return true if \p BB is assumed dead.
2122	///
2123	/// If \p LivenessAA is not provided it is queried.
2124	bool isAssumedDead(const BasicBlock &BB, const AbstractAttribute *QueryingAA,
2125	const AAIsDead *FnLivenessAA,
2126	DepClassTy DepClass = DepClassTy::OPTIONAL);
2127
2128	/// Check \p Pred on all potential Callees of \p CB.
2129	///
2130	/// This method will evaluate \p Pred with all potential callees of \p CB as
2131	/// input and return true if \p Pred does. If some callees might be unknown
2132	/// this function will return false.
2133	bool checkForAllCallees(
2134	function_ref<bool(ArrayRef<const Function *> Callees)> Pred,
2135	const AbstractAttribute &QueryingAA, const CallBase &CB);
2136
2137	/// Check \p Pred on all (transitive) uses of \p V.
2138	///
2139	/// This method will evaluate \p Pred on all (transitive) uses of the
2140	/// associated value and return true if \p Pred holds every time.
2141	/// If uses are skipped in favor of equivalent ones, e.g., if we look through
2142	/// memory, the \p EquivalentUseCB will be used to give the caller an idea
2143	/// what original used was replaced by a new one (or new ones). The visit is
2144	/// cut short if \p EquivalentUseCB returns false and the function will return
2145	/// false as well.
2146	bool checkForAllUses(function_ref<bool(const Use &, bool &)> Pred,
2147	const AbstractAttribute &QueryingAA, const Value &V,
2148	bool CheckBBLivenessOnly = false,
2149	DepClassTy LivenessDepClass = DepClassTy::OPTIONAL,
2150	bool IgnoreDroppableUses = true,
2151	function_ref<bool(const Use &OldU, const Use &NewU)>
2152	EquivalentUseCB = nullptr);
2153
2154	/// Emit a remark generically.
2155	///
2156	/// This template function can be used to generically emit a remark. The
2157	/// RemarkKind should be one of the following:
2158	/// - OptimizationRemark to indicate a successful optimization attempt
2159	/// - OptimizationRemarkMissed to report a failed optimization attempt
2160	/// - OptimizationRemarkAnalysis to provide additional information about an
2161	/// optimization attempt
2162	///
2163	/// The remark is built using a callback function \p RemarkCB that takes a
2164	/// RemarkKind as input and returns a RemarkKind.
2165	template <typename RemarkKind, typename RemarkCallBack>
2166	void emitRemark(Instruction *I, StringRef RemarkName,
2167	RemarkCallBack &&RemarkCB) const {
2168	if (!Configuration.OREGetter)
2169	return;
2170
2171	Function *F = I->getFunction();
2172	auto &ORE = Configuration.OREGetter(F);
2173
2174	if (RemarkName.starts_with(Prefix: "OMP"))
2175	ORE.emit([&]() {
2176	return RemarkCB(RemarkKind(Configuration.PassName, RemarkName, I))
2177	<< " [" << RemarkName << "]";
2178	});
2179	else
2180	ORE.emit([&]() {
2181	return RemarkCB(RemarkKind(Configuration.PassName, RemarkName, I));
2182	});
2183	}
2184
2185	/// Emit a remark on a function.
2186	template <typename RemarkKind, typename RemarkCallBack>
2187	void emitRemark(Function *F, StringRef RemarkName,
2188	RemarkCallBack &&RemarkCB) const {
2189	if (!Configuration.OREGetter)
2190	return;
2191
2192	auto &ORE = Configuration.OREGetter(F);
2193
2194	if (RemarkName.starts_with(Prefix: "OMP"))
2195	ORE.emit([&]() {
2196	return RemarkCB(RemarkKind(Configuration.PassName, RemarkName, F))
2197	<< " [" << RemarkName << "]";
2198	});
2199	else
2200	ORE.emit([&]() {
2201	return RemarkCB(RemarkKind(Configuration.PassName, RemarkName, F));
2202	});
2203	}
2204
2205	/// Helper struct used in the communication between an abstract attribute (AA)
2206	/// that wants to change the signature of a function and the Attributor which
2207	/// applies the changes. The struct is partially initialized with the
2208	/// information from the AA (see the constructor). All other members are
2209	/// provided by the Attributor prior to invoking any callbacks.
2210	struct ArgumentReplacementInfo {
2211	/// Callee repair callback type
2212	///
2213	/// The function repair callback is invoked once to rewire the replacement
2214	/// arguments in the body of the new function. The argument replacement info
2215	/// is passed, as build from the registerFunctionSignatureRewrite call, as
2216	/// well as the replacement function and an iteratore to the first
2217	/// replacement argument.
2218	using CalleeRepairCBTy = std::function<void(
2219	const ArgumentReplacementInfo &, Function &, Function::arg_iterator)>;
2220
2221	/// Abstract call site (ACS) repair callback type
2222	///
2223	/// The abstract call site repair callback is invoked once on every abstract
2224	/// call site of the replaced function (\see ReplacedFn). The callback needs
2225	/// to provide the operands for the call to the new replacement function.
2226	/// The number and type of the operands appended to the provided vector
2227	/// (second argument) is defined by the number and types determined through
2228	/// the replacement type vector (\see ReplacementTypes). The first argument
2229	/// is the ArgumentReplacementInfo object registered with the Attributor
2230	/// through the registerFunctionSignatureRewrite call.
2231	using ACSRepairCBTy =
2232	std::function<void(const ArgumentReplacementInfo &, AbstractCallSite,
2233	SmallVectorImpl<Value *> &)>;
2234
2235	/// Simple getters, see the corresponding members for details.
2236	///{
2237
2238	Attributor &getAttributor() const { return A; }
2239	const Function &getReplacedFn() const { return ReplacedFn; }
2240	const Argument &getReplacedArg() const { return ReplacedArg; }
2241	unsigned getNumReplacementArgs() const { return ReplacementTypes.size(); }
2242	const SmallVectorImpl<Type *> &getReplacementTypes() const {
2243	return ReplacementTypes;
2244	}
2245
2246	///}
2247
2248	private:
2249	/// Constructor that takes the argument to be replaced, the types of
2250	/// the replacement arguments, as well as callbacks to repair the call sites
2251	/// and new function after the replacement happened.
2252	ArgumentReplacementInfo(Attributor &A, Argument &Arg,
2253	ArrayRef<Type *> ReplacementTypes,
2254	CalleeRepairCBTy &&CalleeRepairCB,
2255	ACSRepairCBTy &&ACSRepairCB)
2256	: A(A), ReplacedFn(*Arg.getParent()), ReplacedArg(Arg),
2257	ReplacementTypes(ReplacementTypes.begin(), ReplacementTypes.end()),
2258	CalleeRepairCB(std::move(CalleeRepairCB)),
2259	ACSRepairCB(std::move(ACSRepairCB)) {}
2260
2261	/// Reference to the attributor to allow access from the callbacks.
2262	Attributor &A;
2263
2264	/// The "old" function replaced by ReplacementFn.
2265	const Function &ReplacedFn;
2266
2267	/// The "old" argument replaced by new ones defined via ReplacementTypes.
2268	const Argument &ReplacedArg;
2269
2270	/// The types of the arguments replacing ReplacedArg.
2271	const SmallVector<Type *, 8> ReplacementTypes;
2272
2273	/// Callee repair callback, see CalleeRepairCBTy.
2274	const CalleeRepairCBTy CalleeRepairCB;
2275
2276	/// Abstract call site (ACS) repair callback, see ACSRepairCBTy.
2277	const ACSRepairCBTy ACSRepairCB;
2278
2279	/// Allow access to the private members from the Attributor.
2280	friend struct Attributor;
2281	};
2282
2283	/// Check if we can rewrite a function signature.
2284	///
2285	/// The argument \p Arg is replaced with new ones defined by the number,
2286	/// order, and types in \p ReplacementTypes.
2287	///
2288	/// \returns True, if the replacement can be registered, via
2289	/// registerFunctionSignatureRewrite, false otherwise.
2290	bool isValidFunctionSignatureRewrite(Argument &Arg,
2291	ArrayRef<Type *> ReplacementTypes);
2292
2293	/// Register a rewrite for a function signature.
2294	///
2295	/// The argument \p Arg is replaced with new ones defined by the number,
2296	/// order, and types in \p ReplacementTypes. The rewiring at the call sites is
2297	/// done through \p ACSRepairCB and at the callee site through
2298	/// \p CalleeRepairCB.
2299	///
2300	/// \returns True, if the replacement was registered, false otherwise.
2301	bool registerFunctionSignatureRewrite(
2302	Argument &Arg, ArrayRef<Type *> ReplacementTypes,
2303	ArgumentReplacementInfo::CalleeRepairCBTy &&CalleeRepairCB,
2304	ArgumentReplacementInfo::ACSRepairCBTy &&ACSRepairCB);
2305
2306	/// Check \p Pred on all function call sites.
2307	///
2308	/// This method will evaluate \p Pred on call sites and return
2309	/// true if \p Pred holds in every call sites. However, this is only possible
2310	/// all call sites are known, hence the function has internal linkage.
2311	/// If true is returned, \p UsedAssumedInformation is set if assumed
2312	/// information was used to skip or simplify potential call sites.
2313	bool checkForAllCallSites(function_ref<bool(AbstractCallSite)> Pred,
2314	const AbstractAttribute &QueryingAA,
2315	bool RequireAllCallSites,
2316	bool &UsedAssumedInformation);
2317
2318	/// Check \p Pred on all call sites of \p Fn.
2319	///
2320	/// This method will evaluate \p Pred on call sites and return
2321	/// true if \p Pred holds in every call sites. However, this is only possible
2322	/// all call sites are known, hence the function has internal linkage.
2323	/// If true is returned, \p UsedAssumedInformation is set if assumed
2324	/// information was used to skip or simplify potential call sites.
2325	bool checkForAllCallSites(function_ref<bool(AbstractCallSite)> Pred,
2326	const Function &Fn, bool RequireAllCallSites,
2327	const AbstractAttribute *QueryingAA,
2328	bool &UsedAssumedInformation,
2329	bool CheckPotentiallyDead = false);
2330
2331	/// Check \p Pred on all values potentially returned by the function
2332	/// associated with \p QueryingAA.
2333	///
2334	/// This is the context insensitive version of the method above.
2335	bool
2336	checkForAllReturnedValues(function_ref<bool(Value &)> Pred,
2337	const AbstractAttribute &QueryingAA,
2338	AA::ValueScope S = AA::ValueScope::Intraprocedural,
2339	bool RecurseForSelectAndPHI = true);
2340
2341	/// Check \p Pred on all instructions in \p Fn with an opcode present in
2342	/// \p Opcodes.
2343	///
2344	/// This method will evaluate \p Pred on all instructions with an opcode
2345	/// present in \p Opcode and return true if \p Pred holds on all of them.
2346	bool checkForAllInstructions(function_ref<bool(Instruction &)> Pred,
2347	const Function *Fn,
2348	const AbstractAttribute *QueryingAA,
2349	ArrayRef<unsigned> Opcodes,
2350	bool &UsedAssumedInformation,
2351	bool CheckBBLivenessOnly = false,
2352	bool CheckPotentiallyDead = false);
2353
2354	/// Check \p Pred on all instructions with an opcode present in \p Opcodes.
2355	///
2356	/// This method will evaluate \p Pred on all instructions with an opcode
2357	/// present in \p Opcode and return true if \p Pred holds on all of them.
2358	bool checkForAllInstructions(function_ref<bool(Instruction &)> Pred,
2359	const AbstractAttribute &QueryingAA,
2360	ArrayRef<unsigned> Opcodes,
2361	bool &UsedAssumedInformation,
2362	bool CheckBBLivenessOnly = false,
2363	bool CheckPotentiallyDead = false);
2364
2365	/// Check \p Pred on all call-like instructions (=CallBased derived).
2366	///
2367	/// See checkForAllCallLikeInstructions(...) for more information.
2368	bool checkForAllCallLikeInstructions(function_ref<bool(Instruction &)> Pred,
2369	const AbstractAttribute &QueryingAA,
2370	bool &UsedAssumedInformation,
2371	bool CheckBBLivenessOnly = false,
2372	bool CheckPotentiallyDead = false) {
2373	return checkForAllInstructions(
2374	Pred, QueryingAA,
2375	Opcodes: {(unsigned)Instruction::Invoke, (unsigned)Instruction::CallBr,
2376	(unsigned)Instruction::Call},
2377	UsedAssumedInformation, CheckBBLivenessOnly, CheckPotentiallyDead);
2378	}
2379
2380	/// Check \p Pred on all Read/Write instructions.
2381	///
2382	/// This method will evaluate \p Pred on all instructions that read or write
2383	/// to memory present in the information cache and return true if \p Pred
2384	/// holds on all of them.
2385	bool checkForAllReadWriteInstructions(function_ref<bool(Instruction &)> Pred,
2386	AbstractAttribute &QueryingAA,
2387	bool &UsedAssumedInformation);
2388
2389	/// Create a shallow wrapper for \p F such that \p F has internal linkage
2390	/// afterwards. It also sets the original \p F 's name to anonymous
2391	///
2392	/// A wrapper is a function with the same type (and attributes) as \p F
2393	/// that will only call \p F and return the result, if any.
2394	///
2395	/// Assuming the declaration of looks like:
2396	/// rty F(aty0 arg0, ..., atyN argN);
2397	///
2398	/// The wrapper will then look as follows:
2399	/// rty wrapper(aty0 arg0, ..., atyN argN) {
2400	/// return F(arg0, ..., argN);
2401	/// }
2402	///
2403	static void createShallowWrapper(Function &F);
2404
2405	/// Returns true if the function \p F can be internalized. i.e. it has a
2406	/// compatible linkage.
2407	static bool isInternalizable(Function &F);
2408
2409	/// Make another copy of the function \p F such that the copied version has
2410	/// internal linkage afterwards and can be analysed. Then we replace all uses
2411	/// of the original function to the copied one
2412	///
2413	/// Only non-locally linked functions that have `linkonce_odr` or `weak_odr`
2414	/// linkage can be internalized because these linkages guarantee that other
2415	/// definitions with the same name have the same semantics as this one.
2416	///
2417	/// This will only be run if the `attributor-allow-deep-wrappers` option is
2418	/// set, or if the function is called with \p Force set to true.
2419	///
2420	/// If the function \p F failed to be internalized the return value will be a
2421	/// null pointer.
2422	static Function *internalizeFunction(Function &F, bool Force = false);
2423
2424	/// Make copies of each function in the set \p FnSet such that the copied
2425	/// version has internal linkage afterwards and can be analysed. Then we
2426	/// replace all uses of the original function to the copied one. The map
2427	/// \p FnMap contains a mapping of functions to their internalized versions.
2428	///
2429	/// Only non-locally linked functions that have `linkonce_odr` or `weak_odr`
2430	/// linkage can be internalized because these linkages guarantee that other
2431	/// definitions with the same name have the same semantics as this one.
2432	///
2433	/// This version will internalize all the functions in the set \p FnSet at
2434	/// once and then replace the uses. This prevents internalized functions being
2435	/// called by external functions when there is an internalized version in the
2436	/// module.
2437	static bool internalizeFunctions(SmallPtrSetImpl<Function *> &FnSet,
2438	DenseMap<Function *, Function *> &FnMap);
2439
2440	/// Return the data layout associated with the anchor scope.
2441	const DataLayout &getDataLayout() const { return InfoCache.DL; }
2442
2443	/// The allocator used to allocate memory, e.g. for `AbstractAttribute`s.
2444	BumpPtrAllocator &Allocator;
2445
2446	const SmallSetVector<Function *, 8> &getModifiedFunctions() {
2447	return CGModifiedFunctions;
2448	}
2449
2450	private:
2451	/// This method will do fixpoint iteration until fixpoint or the
2452	/// maximum iteration count is reached.
2453	///
2454	/// If the maximum iteration count is reached, This method will
2455	/// indicate pessimistic fixpoint on attributes that transitively depend
2456	/// on attributes that were scheduled for an update.
2457	void runTillFixpoint();
2458
2459	/// Gets called after scheduling, manifests attributes to the LLVM IR.
2460	ChangeStatus manifestAttributes();
2461
2462	/// Gets called after attributes have been manifested, cleans up the IR.
2463	/// Deletes dead functions, blocks and instructions.
2464	/// Rewrites function signitures and updates the call graph.
2465	ChangeStatus cleanupIR();
2466
2467	/// Identify internal functions that are effectively dead, thus not reachable
2468	/// from a live entry point. The functions are added to ToBeDeletedFunctions.
2469	void identifyDeadInternalFunctions();
2470
2471	/// Run `::update` on \p AA and track the dependences queried while doing so.
2472	/// Also adjust the state if we know further updates are not necessary.
2473	ChangeStatus updateAA(AbstractAttribute &AA);
2474
2475	/// Remember the dependences on the top of the dependence stack such that they
2476	/// may trigger further updates. (\see DependenceStack)
2477	void rememberDependences();
2478
2479	/// Determine if CallBase context in \p IRP should be propagated.
2480	bool shouldPropagateCallBaseContext(const IRPosition &IRP);
2481
2482	/// Apply all requested function signature rewrites
2483	/// (\see registerFunctionSignatureRewrite) and return Changed if the module
2484	/// was altered.
2485	ChangeStatus
2486	rewriteFunctionSignatures(SmallSetVector<Function *, 8> &ModifiedFns);
2487
2488	/// Check if the Attribute \p AA should be seeded.
2489	/// See getOrCreateAAFor.
2490	bool shouldSeedAttribute(AbstractAttribute &AA);
2491
2492	/// A nested map to lookup abstract attributes based on the argument position
2493	/// on the outer level, and the addresses of the static member (AAType::ID) on
2494	/// the inner level.
2495	///{
2496	using AAMapKeyTy = std::pair<const char *, IRPosition>;
2497	DenseMap<AAMapKeyTy, AbstractAttribute *> AAMap;
2498	///}
2499
2500	/// Map to remember all requested signature changes (= argument replacements).
2501	DenseMap<Function *, SmallVector<std::unique_ptr<ArgumentReplacementInfo>, 8>>
2502	ArgumentReplacementMap;
2503
2504	/// The set of functions we are deriving attributes for.
2505	SetVector<Function *> &Functions;
2506
2507	/// The information cache that holds pre-processed (LLVM-IR) information.
2508	InformationCache &InfoCache;
2509
2510	/// Abstract Attribute dependency graph
2511	AADepGraph DG;
2512
2513	/// Set of functions for which we modified the content such that it might
2514	/// impact the call graph.
2515	SmallSetVector<Function *, 8> CGModifiedFunctions;
2516
2517	/// Information about a dependence. If FromAA is changed ToAA needs to be
2518	/// updated as well.
2519	struct DepInfo {
2520	const AbstractAttribute *FromAA;
2521	const AbstractAttribute *ToAA;
2522	DepClassTy DepClass;
2523	};
2524
2525	/// The dependence stack is used to track dependences during an
2526	/// `AbstractAttribute::update` call. As `AbstractAttribute::update` can be
2527	/// recursive we might have multiple vectors of dependences in here. The stack
2528	/// size, should be adjusted according to the expected recursion depth and the
2529	/// inner dependence vector size to the expected number of dependences per
2530	/// abstract attribute. Since the inner vectors are actually allocated on the
2531	/// stack we can be generous with their size.
2532	using DependenceVector = SmallVector<DepInfo, 8>;
2533	SmallVector<DependenceVector *, 16> DependenceStack;
2534
2535	/// A set to remember the functions we already assume to be live and visited.
2536	DenseSet<const Function *> VisitedFunctions;
2537
2538	/// Uses we replace with a new value after manifest is done. We will remove
2539	/// then trivially dead instructions as well.
2540	SmallMapVector<Use *, Value *, 32> ToBeChangedUses;
2541
2542	/// Values we replace with a new value after manifest is done. We will remove
2543	/// then trivially dead instructions as well.
2544	SmallMapVector<Value *, PointerIntPair<Value *, 1, bool>, 32>
2545	ToBeChangedValues;
2546
2547	/// Instructions we replace with `unreachable` insts after manifest is done.
2548	SmallSetVector<WeakVH, 16> ToBeChangedToUnreachableInsts;
2549
2550	/// Invoke instructions with at least a single dead successor block.
2551	SmallSetVector<WeakVH, 16> InvokeWithDeadSuccessor;
2552
2553	/// A flag that indicates which stage of the process we are in. Initially, the
2554	/// phase is SEEDING. Phase is changed in `Attributor::run()`
2555	enum class AttributorPhase {
2556	SEEDING,
2557	UPDATE,
2558	MANIFEST,
2559	CLEANUP,
2560	} Phase = AttributorPhase::SEEDING;
2561
2562	/// The current initialization chain length. Tracked to avoid stack overflows.
2563	unsigned InitializationChainLength = 0;
2564
2565	/// Functions, blocks, and instructions we delete after manifest is done.
2566	///
2567	///{
2568	SmallPtrSet<BasicBlock *, 8> ManifestAddedBlocks;
2569	SmallSetVector<Function *, 8> ToBeDeletedFunctions;
2570	SmallSetVector<BasicBlock *, 8> ToBeDeletedBlocks;
2571	SmallSetVector<WeakVH, 8> ToBeDeletedInsts;
2572	///}
2573
2574	/// Container with all the query AAs that requested an update via
2575	/// registerForUpdate.
2576	SmallSetVector<AbstractAttribute *, 16> QueryAAsAwaitingUpdate;
2577
2578	/// User provided configuration for this Attributor instance.
2579	const AttributorConfig Configuration;
2580
2581	friend AADepGraph;
2582	friend AttributorCallGraph;
2583	};
2584
2585	/// An interface to query the internal state of an abstract attribute.
2586	///
2587	/// The abstract state is a minimal interface that allows the Attributor to
2588	/// communicate with the abstract attributes about their internal state without
2589	/// enforcing or exposing implementation details, e.g., the (existence of an)
2590	/// underlying lattice.
2591	///
2592	/// It is sufficient to be able to query if a state is (1) valid or invalid, (2)
2593	/// at a fixpoint, and to indicate to the state that (3) an optimistic fixpoint
2594	/// was reached or (4) a pessimistic fixpoint was enforced.
2595	///
2596	/// All methods need to be implemented by the subclass. For the common use case,
2597	/// a single boolean state or a bit-encoded state, the BooleanState and
2598	/// {Inc,Dec,Bit}IntegerState classes are already provided. An abstract
2599	/// attribute can inherit from them to get the abstract state interface and
2600	/// additional methods to directly modify the state based if needed. See the
2601	/// class comments for help.
2602	struct AbstractState {
2603	virtual ~AbstractState() = default;
2604
2605	/// Return if this abstract state is in a valid state. If false, no
2606	/// information provided should be used.
2607	virtual bool isValidState() const = 0;
2608
2609	/// Return if this abstract state is fixed, thus does not need to be updated
2610	/// if information changes as it cannot change itself.
2611	virtual bool isAtFixpoint() const = 0;
2612
2613	/// Indicate that the abstract state should converge to the optimistic state.
2614	///
2615	/// This will usually make the optimistically assumed state the known to be
2616	/// true state.
2617	///
2618	/// \returns ChangeStatus::UNCHANGED as the assumed value should not change.
2619	virtual ChangeStatus indicateOptimisticFixpoint() = 0;
2620
2621	/// Indicate that the abstract state should converge to the pessimistic state.
2622	///
2623	/// This will usually revert the optimistically assumed state to the known to
2624	/// be true state.
2625	///
2626	/// \returns ChangeStatus::CHANGED as the assumed value may change.
2627	virtual ChangeStatus indicatePessimisticFixpoint() = 0;
2628	};
2629
2630	/// Simple state with integers encoding.
2631	///
2632	/// The interface ensures that the assumed bits are always a subset of the known
2633	/// bits. Users can only add known bits and, except through adding known bits,
2634	/// they can only remove assumed bits. This should guarantee monotonicity and
2635	/// thereby the existence of a fixpoint (if used correctly). The fixpoint is
2636	/// reached when the assumed and known state/bits are equal. Users can
2637	/// force/inidicate a fixpoint. If an optimistic one is indicated, the known
2638	/// state will catch up with the assumed one, for a pessimistic fixpoint it is
2639	/// the other way around.
2640	template <typename base_ty, base_ty BestState, base_ty WorstState>
2641	struct IntegerStateBase : public AbstractState {
2642	using base_t = base_ty;
2643
2644	IntegerStateBase() = default;
2645	IntegerStateBase(base_t Assumed) : Assumed(Assumed) {}
2646
2647	/// Return the best possible representable state.
2648	static constexpr base_t getBestState() { return BestState; }
2649	static constexpr base_t getBestState(const IntegerStateBase &) {
2650	return getBestState();
2651	}
2652
2653	/// Return the worst possible representable state.
2654	static constexpr base_t getWorstState() { return WorstState; }
2655	static constexpr base_t getWorstState(const IntegerStateBase &) {
2656	return getWorstState();
2657	}
2658
2659	/// See AbstractState::isValidState()
2660	/// NOTE: For now we simply pretend that the worst possible state is invalid.
2661	bool isValidState() const override { return Assumed != getWorstState(); }
2662
2663	/// See AbstractState::isAtFixpoint()
2664	bool isAtFixpoint() const override { return Assumed == Known; }
2665
2666	/// See AbstractState::indicateOptimisticFixpoint(...)
2667	ChangeStatus indicateOptimisticFixpoint() override {
2668	Known = Assumed;
2669	return ChangeStatus::UNCHANGED;
2670	}
2671
2672	/// See AbstractState::indicatePessimisticFixpoint(...)
2673	ChangeStatus indicatePessimisticFixpoint() override {
2674	Assumed = Known;
2675	return ChangeStatus::CHANGED;
2676	}
2677
2678	/// Return the known state encoding
2679	base_t getKnown() const { return Known; }
2680
2681	/// Return the assumed state encoding.
2682	base_t getAssumed() const { return Assumed; }
2683
2684	/// Equality for IntegerStateBase.
2685	bool
2686	operator==(const IntegerStateBase<base_t, BestState, WorstState> &R) const {
2687	return this->getAssumed() == R.getAssumed() &&
2688	this->getKnown() == R.getKnown();
2689	}
2690
2691	/// Inequality for IntegerStateBase.
2692	bool
2693	operator!=(const IntegerStateBase<base_t, BestState, WorstState> &R) const {
2694	return !(*this == R);
2695	}
2696
2697	/// "Clamp" this state with \p R. The result is subtype dependent but it is
2698	/// intended that only information assumed in both states will be assumed in
2699	/// this one afterwards.
2700	void operator^=(const IntegerStateBase<base_t, BestState, WorstState> &R) {
2701	handleNewAssumedValue(Value: R.getAssumed());
2702	}
2703
2704	/// "Clamp" this state with \p R. The result is subtype dependent but it is
2705	/// intended that information known in either state will be known in
2706	/// this one afterwards.
2707	void operator+=(const IntegerStateBase<base_t, BestState, WorstState> &R) {
2708	handleNewKnownValue(Value: R.getKnown());
2709	}
2710
2711	void operator|=(const IntegerStateBase<base_t, BestState, WorstState> &R) {
2712	joinOR(AssumedValue: R.getAssumed(), KnownValue: R.getKnown());
2713	}
2714
2715	void operator&=(const IntegerStateBase<base_t, BestState, WorstState> &R) {
2716	joinAND(AssumedValue: R.getAssumed(), KnownValue: R.getKnown());
2717	}
2718
2719	protected:
2720	/// Handle a new assumed value \p Value. Subtype dependent.
2721	virtual void handleNewAssumedValue(base_t Value) = 0;
2722
2723	/// Handle a new known value \p Value. Subtype dependent.
2724	virtual void handleNewKnownValue(base_t Value) = 0;
2725
2726	/// Handle a value \p Value. Subtype dependent.
2727	virtual void joinOR(base_t AssumedValue, base_t KnownValue) = 0;
2728
2729	/// Handle a new assumed value \p Value. Subtype dependent.
2730	virtual void joinAND(base_t AssumedValue, base_t KnownValue) = 0;
2731
2732	/// The known state encoding in an integer of type base_t.
2733	base_t Known = getWorstState();
2734
2735	/// The assumed state encoding in an integer of type base_t.
2736	base_t Assumed = getBestState();
2737	};
2738
2739	/// Specialization of the integer state for a bit-wise encoding.
2740	template <typename base_ty = uint32_t, base_ty BestState = ~base_ty(0),
2741	base_ty WorstState = 0>
2742	struct BitIntegerState
2743	: public IntegerStateBase<base_ty, BestState, WorstState> {
2744	using super = IntegerStateBase<base_ty, BestState, WorstState>;
2745	using base_t = base_ty;
2746	BitIntegerState() = default;
2747	BitIntegerState(base_t Assumed) : super(Assumed) {}
2748
2749	/// Return true if the bits set in \p BitsEncoding are "known bits".
2750	bool isKnown(base_t BitsEncoding = BestState) const {
2751	return (this->Known & BitsEncoding) == BitsEncoding;
2752	}
2753
2754	/// Return true if the bits set in \p BitsEncoding are "assumed bits".
2755	bool isAssumed(base_t BitsEncoding = BestState) const {
2756	return (this->Assumed & BitsEncoding) == BitsEncoding;
2757	}
2758
2759	/// Add the bits in \p BitsEncoding to the "known bits".
2760	BitIntegerState &addKnownBits(base_t Bits) {
2761	// Make sure we never miss any "known bits".
2762	this->Assumed |= Bits;
2763	this->Known |= Bits;
2764	return *this;
2765	}
2766
2767	/// Remove the bits in \p BitsEncoding from the "assumed bits" if not known.
2768	BitIntegerState &removeAssumedBits(base_t BitsEncoding) {
2769	return intersectAssumedBits(BitsEncoding: ~BitsEncoding);
2770	}
2771
2772	/// Remove the bits in \p BitsEncoding from the "known bits".
2773	BitIntegerState &removeKnownBits(base_t BitsEncoding) {
2774	this->Known = (this->Known & ~BitsEncoding);
2775	return *this;
2776	}
2777
2778	/// Keep only "assumed bits" also set in \p BitsEncoding but all known ones.
2779	BitIntegerState &intersectAssumedBits(base_t BitsEncoding) {
2780	// Make sure we never lose any "known bits".
2781	this->Assumed = (this->Assumed & BitsEncoding) | this->Known;
2782	return *this;
2783	}
2784
2785	private:
2786	void handleNewAssumedValue(base_t Value) override {
2787	intersectAssumedBits(BitsEncoding: Value);
2788	}
2789	void handleNewKnownValue(base_t Value) override { addKnownBits(Bits: Value); }
2790	void joinOR(base_t AssumedValue, base_t KnownValue) override {
2791	this->Known |= KnownValue;
2792	this->Assumed |= AssumedValue;
2793	}
2794	void joinAND(base_t AssumedValue, base_t KnownValue) override {
2795	this->Known &= KnownValue;
2796	this->Assumed &= AssumedValue;
2797	}
2798	};
2799
2800	/// Specialization of the integer state for an increasing value, hence ~0u is
2801	/// the best state and 0 the worst.
2802	template <typename base_ty = uint32_t, base_ty BestState = ~base_ty(0),
2803	base_ty WorstState = 0>
2804	struct IncIntegerState
2805	: public IntegerStateBase<base_ty, BestState, WorstState> {
2806	using super = IntegerStateBase<base_ty, BestState, WorstState>;
2807	using base_t = base_ty;
2808
2809	IncIntegerState() : super() {}
2810	IncIntegerState(base_t Assumed) : super(Assumed) {}
2811
2812	/// Return the best possible representable state.
2813	static constexpr base_t getBestState() { return BestState; }
2814	static constexpr base_t
2815	getBestState(const IncIntegerState<base_ty, BestState, WorstState> &) {
2816	return getBestState();
2817	}
2818
2819	/// Take minimum of assumed and \p Value.
2820	IncIntegerState &takeAssumedMinimum(base_t Value) {
2821	// Make sure we never lose "known value".
2822	this->Assumed = std::max(std::min(this->Assumed, Value), this->Known);
2823	return *this;
2824	}
2825
2826	/// Take maximum of known and \p Value.
2827	IncIntegerState &takeKnownMaximum(base_t Value) {
2828	// Make sure we never lose "known value".
2829	this->Assumed = std::max(Value, this->Assumed);
2830	this->Known = std::max(Value, this->Known);
2831	return *this;
2832	}
2833
2834	private:
2835	void handleNewAssumedValue(base_t Value) override {
2836	takeAssumedMinimum(Value);
2837	}
2838	void handleNewKnownValue(base_t Value) override { takeKnownMaximum(Value); }
2839	void joinOR(base_t AssumedValue, base_t KnownValue) override {
2840	this->Known = std::max(this->Known, KnownValue);
2841	this->Assumed = std::max(this->Assumed, AssumedValue);
2842	}
2843	void joinAND(base_t AssumedValue, base_t KnownValue) override {
2844	this->Known = std::min(this->Known, KnownValue);
2845	this->Assumed = std::min(this->Assumed, AssumedValue);
2846	}
2847	};
2848
2849	/// Specialization of the integer state for a decreasing value, hence 0 is the
2850	/// best state and ~0u the worst.
2851	template <typename base_ty = uint32_t>
2852	struct DecIntegerState : public IntegerStateBase<base_ty, 0, ~base_ty(0)> {
2853	using base_t = base_ty;
2854
2855	/// Take maximum of assumed and \p Value.
2856	DecIntegerState &takeAssumedMaximum(base_t Value) {
2857	// Make sure we never lose "known value".
2858	this->Assumed = std::min(std::max(this->Assumed, Value), this->Known);
2859	return *this;
2860	}
2861
2862	/// Take minimum of known and \p Value.
2863	DecIntegerState &takeKnownMinimum(base_t Value) {
2864	// Make sure we never lose "known value".
2865	this->Assumed = std::min(Value, this->Assumed);
2866	this->Known = std::min(Value, this->Known);
2867	return *this;
2868	}
2869
2870	private:
2871	void handleNewAssumedValue(base_t Value) override {
2872	takeAssumedMaximum(Value);
2873	}
2874	void handleNewKnownValue(base_t Value) override { takeKnownMinimum(Value); }
2875	void joinOR(base_t AssumedValue, base_t KnownValue) override {
2876	this->Assumed = std::min(this->Assumed, KnownValue);
2877	this->Assumed = std::min(this->Assumed, AssumedValue);
2878	}
2879	void joinAND(base_t AssumedValue, base_t KnownValue) override {
2880	this->Assumed = std::max(this->Assumed, KnownValue);
2881	this->Assumed = std::max(this->Assumed, AssumedValue);
2882	}
2883	};
2884
2885	/// Simple wrapper for a single bit (boolean) state.
2886	struct BooleanState : public IntegerStateBase<bool, true, false> {
2887	using super = IntegerStateBase<bool, true, false>;
2888	using base_t = IntegerStateBase::base_t;
2889
2890	BooleanState() = default;
2891	BooleanState(base_t Assumed) : super(Assumed) {}
2892
2893	/// Set the assumed value to \p Value but never below the known one.
2894	void setAssumed(bool Value) { Assumed &= (Known | Value); }
2895
2896	/// Set the known and asssumed value to \p Value.
2897	void setKnown(bool Value) {
2898	Known |= Value;
2899	Assumed |= Value;
2900	}
2901
2902	/// Return true if the state is assumed to hold.
2903	bool isAssumed() const { return getAssumed(); }
2904
2905	/// Return true if the state is known to hold.
2906	bool isKnown() const { return getKnown(); }
2907
2908	private:
2909	void handleNewAssumedValue(base_t Value) override {
2910	if (!Value)
2911	Assumed = Known;
2912	}
2913	void handleNewKnownValue(base_t Value) override {
2914	if (Value)
2915	Known = (Assumed = Value);
2916	}
2917	void joinOR(base_t AssumedValue, base_t KnownValue) override {
2918	Known |= KnownValue;
2919	Assumed |= AssumedValue;
2920	}
2921	void joinAND(base_t AssumedValue, base_t KnownValue) override {
2922	Known &= KnownValue;
2923	Assumed &= AssumedValue;
2924	}
2925	};
2926
2927	/// State for an integer range.
2928	struct IntegerRangeState : public AbstractState {
2929
2930	/// Bitwidth of the associated value.
2931	uint32_t BitWidth;
2932
2933	/// State representing assumed range, initially set to empty.
2934	ConstantRange Assumed;
2935
2936	/// State representing known range, initially set to [-inf, inf].
2937	ConstantRange Known;
2938
2939	IntegerRangeState(uint32_t BitWidth)
2940	: BitWidth(BitWidth), Assumed(ConstantRange::getEmpty(BitWidth)),
2941	Known(ConstantRange::getFull(BitWidth)) {}
2942
2943	IntegerRangeState(const ConstantRange &CR)
2944	: BitWidth(CR.getBitWidth()), Assumed(CR),
2945	Known(getWorstState(BitWidth: CR.getBitWidth())) {}
2946
2947	/// Return the worst possible representable state.
2948	static ConstantRange getWorstState(uint32_t BitWidth) {
2949	return ConstantRange::getFull(BitWidth);
2950	}
2951
2952	/// Return the best possible representable state.
2953	static ConstantRange getBestState(uint32_t BitWidth) {
2954	return ConstantRange::getEmpty(BitWidth);
2955	}
2956	static ConstantRange getBestState(const IntegerRangeState &IRS) {
2957	return getBestState(BitWidth: IRS.getBitWidth());
2958	}
2959
2960	/// Return associated values' bit width.
2961	uint32_t getBitWidth() const { return BitWidth; }
2962
2963	/// See AbstractState::isValidState()
2964	bool isValidState() const override {
2965	return BitWidth > 0 && !Assumed.isFullSet();
2966	}
2967
2968	/// See AbstractState::isAtFixpoint()
2969	bool isAtFixpoint() const override { return Assumed == Known; }
2970
2971	/// See AbstractState::indicateOptimisticFixpoint(...)
2972	ChangeStatus indicateOptimisticFixpoint() override {
2973	Known = Assumed;
2974	return ChangeStatus::CHANGED;
2975	}
2976
2977	/// See AbstractState::indicatePessimisticFixpoint(...)
2978	ChangeStatus indicatePessimisticFixpoint() override {
2979	Assumed = Known;
2980	return ChangeStatus::CHANGED;
2981	}
2982
2983	/// Return the known state encoding
2984	ConstantRange getKnown() const { return Known; }
2985
2986	/// Return the assumed state encoding.
2987	ConstantRange getAssumed() const { return Assumed; }
2988
2989	/// Unite assumed range with the passed state.
2990	void unionAssumed(const ConstantRange &R) {
2991	// Don't lose a known range.
2992	Assumed = Assumed.unionWith(CR: R).intersectWith(CR: Known);
2993	}
2994
2995	/// See IntegerRangeState::unionAssumed(..).
2996	void unionAssumed(const IntegerRangeState &R) {
2997	unionAssumed(R: R.getAssumed());
2998	}
2999
3000	/// Intersect known range with the passed state.
3001	void intersectKnown(const ConstantRange &R) {
3002	Assumed = Assumed.intersectWith(CR: R);
3003	Known = Known.intersectWith(CR: R);
3004	}
3005
3006	/// See IntegerRangeState::intersectKnown(..).
3007	void intersectKnown(const IntegerRangeState &R) {
3008	intersectKnown(R: R.getKnown());
3009	}
3010
3011	/// Equality for IntegerRangeState.
3012	bool operator==(const IntegerRangeState &R) const {
3013	return getAssumed() == R.getAssumed() && getKnown() == R.getKnown();
3014	}
3015
3016	/// "Clamp" this state with \p R. The result is subtype dependent but it is
3017	/// intended that only information assumed in both states will be assumed in
3018	/// this one afterwards.
3019	IntegerRangeState operator^=(const IntegerRangeState &R) {
3020	// NOTE: `^=` operator seems like `intersect` but in this case, we need to
3021	// take `union`.
3022	unionAssumed(R);
3023	return *this;
3024	}
3025
3026	IntegerRangeState operator&=(const IntegerRangeState &R) {
3027	// NOTE: `&=` operator seems like `intersect` but in this case, we need to
3028	// take `union`.
3029	Known = Known.unionWith(CR: R.getKnown());
3030	Assumed = Assumed.unionWith(CR: R.getAssumed());
3031	return *this;
3032	}
3033	};
3034
3035	/// Simple state for a set.
3036	///
3037	/// This represents a state containing a set of values. The interface supports
3038	/// modelling sets that contain all possible elements. The state's internal
3039	/// value is modified using union or intersection operations.
3040	template <typename BaseTy> struct SetState : public AbstractState {
3041	/// A wrapper around a set that has semantics for handling unions and
3042	/// intersections with a "universal" set that contains all elements.
3043	struct SetContents {
3044	/// Creates a universal set with no concrete elements or an empty set.
3045	SetContents(bool Universal) : Universal(Universal) {}
3046
3047	/// Creates a non-universal set with concrete values.
3048	SetContents(const DenseSet<BaseTy> &Assumptions)
3049	: Universal(false), Set(Assumptions) {}
3050
3051	SetContents(bool Universal, const DenseSet<BaseTy> &Assumptions)
3052	: Universal(Universal), Set(Assumptions) {}
3053
3054	const DenseSet<BaseTy> &getSet() const { return Set; }
3055
3056	bool isUniversal() const { return Universal; }
3057
3058	bool empty() const { return Set.empty() && !Universal; }
3059
3060	/// Finds A := A ^ B where A or B could be the "Universal" set which
3061	/// contains every possible attribute. Returns true if changes were made.
3062	bool getIntersection(const SetContents &RHS) {
3063	bool IsUniversal = Universal;
3064	unsigned Size = Set.size();
3065
3066	// A := A ^ U = A
3067	if (RHS.isUniversal())
3068	return false;
3069
3070	// A := U ^ B = B
3071	if (Universal)
3072	Set = RHS.getSet();
3073	else
3074	set_intersect(Set, RHS.getSet());
3075
3076	Universal &= RHS.isUniversal();
3077	return IsUniversal != Universal || Size != Set.size();
3078	}
3079
3080	/// Finds A := A u B where A or B could be the "Universal" set which
3081	/// contains every possible attribute. returns true if changes were made.
3082	bool getUnion(const SetContents &RHS) {
3083	bool IsUniversal = Universal;
3084	unsigned Size = Set.size();
3085
3086	// A := A u U = U = U u B
3087	if (!RHS.isUniversal() && !Universal)
3088	set_union(Set, RHS.getSet());
3089
3090	Universal |= RHS.isUniversal();
3091	return IsUniversal != Universal || Size != Set.size();
3092	}
3093
3094	private:
3095	/// Indicates if this set is "universal", containing every possible element.
3096	bool Universal;
3097
3098	/// The set of currently active assumptions.
3099	DenseSet<BaseTy> Set;
3100	};
3101
3102	SetState() : Known(false), Assumed(true), IsAtFixedpoint(false) {}
3103
3104	/// Initializes the known state with an initial set and initializes the
3105	/// assumed state as universal.
3106	SetState(const DenseSet<BaseTy> &Known)
3107	: Known(Known), Assumed(true), IsAtFixedpoint(false) {}
3108
3109	/// See AbstractState::isValidState()
3110	bool isValidState() const override { return !Assumed.empty(); }
3111
3112	/// See AbstractState::isAtFixpoint()
3113	bool isAtFixpoint() const override { return IsAtFixedpoint; }
3114
3115	/// See AbstractState::indicateOptimisticFixpoint(...)
3116	ChangeStatus indicateOptimisticFixpoint() override {
3117	IsAtFixedpoint = true;
3118	Known = Assumed;
3119	return ChangeStatus::UNCHANGED;
3120	}
3121
3122	/// See AbstractState::indicatePessimisticFixpoint(...)
3123	ChangeStatus indicatePessimisticFixpoint() override {
3124	IsAtFixedpoint = true;
3125	Assumed = Known;
3126	return ChangeStatus::CHANGED;
3127	}
3128
3129	/// Return the known state encoding.
3130	const SetContents &getKnown() const { return Known; }
3131
3132	/// Return the assumed state encoding.
3133	const SetContents &getAssumed() const { return Assumed; }
3134
3135	/// Returns if the set state contains the element.
3136	bool setContains(const BaseTy &Elem) const {
3137	return Assumed.getSet().contains(Elem) || Known.getSet().contains(Elem);
3138	}
3139
3140	/// Performs the set intersection between this set and \p RHS. Returns true if
3141	/// changes were made.
3142	bool getIntersection(const SetContents &RHS) {
3143	bool IsUniversal = Assumed.isUniversal();
3144	unsigned SizeBefore = Assumed.getSet().size();
3145
3146	// Get intersection and make sure that the known set is still a proper
3147	// subset of the assumed set. A := K u (A ^ R).
3148	Assumed.getIntersection(RHS);
3149	Assumed.getUnion(Known);
3150
3151	return SizeBefore != Assumed.getSet().size() ||
3152	IsUniversal != Assumed.isUniversal();
3153	}
3154
3155	/// Performs the set union between this set and \p RHS. Returns true if
3156	/// changes were made.
3157	bool getUnion(const SetContents &RHS) { return Assumed.getUnion(RHS); }
3158
3159	private:
3160	/// The set of values known for this state.
3161	SetContents Known;
3162
3163	/// The set of assumed values for this state.
3164	SetContents Assumed;
3165
3166	bool IsAtFixedpoint;
3167	};
3168
3169	/// Helper to tie a abstract state implementation to an abstract attribute.
3170	template <typename StateTy, typename BaseType, class... Ts>
3171	struct StateWrapper : public BaseType, public StateTy {
3172	/// Provide static access to the type of the state.
3173	using StateType = StateTy;
3174
3175	StateWrapper(const IRPosition &IRP, Ts... Args)
3176	: BaseType(IRP), StateTy(Args...) {}
3177
3178	/// See AbstractAttribute::getState(...).
3179	StateType &getState() override { return *this; }
3180
3181	/// See AbstractAttribute::getState(...).
3182	const StateType &getState() const override { return *this; }
3183	};
3184
3185	/// Helper class that provides common functionality to manifest IR attributes.
3186	template <Attribute::AttrKind AK, typename BaseType, typename AAType>
3187	struct IRAttribute : public BaseType {
3188	IRAttribute(const IRPosition &IRP) : BaseType(IRP) {}
3189
3190	/// Most boolean IRAttribute AAs don't do anything non-trivial
3191	/// in their initializers while non-boolean ones often do. Subclasses can
3192	/// change this.
3193	static bool hasTrivialInitializer() { return Attribute::isEnumAttrKind(Kind: AK); }
3194
3195	/// Compile time access to the IR attribute kind.
3196	static constexpr Attribute::AttrKind IRAttributeKind = AK;
3197
3198	/// Return true if the IR attribute(s) associated with this AA are implied for
3199	/// an undef value.
3200	static bool isImpliedByUndef() { return true; }
3201
3202	/// Return true if the IR attribute(s) associated with this AA are implied for
3203	/// an poison value.
3204	static bool isImpliedByPoison() { return true; }
3205
3206	static bool isImpliedByIR(Attributor &A, const IRPosition &IRP,
3207	Attribute::AttrKind ImpliedAttributeKind = AK,
3208	bool IgnoreSubsumingPositions = false) {
3209	if (AAType::isImpliedByUndef() && isa<UndefValue>(Val: IRP.getAssociatedValue()))
3210	return true;
3211	if (AAType::isImpliedByPoison() &&
3212	isa<PoisonValue>(Val: IRP.getAssociatedValue()))
3213	return true;
3214	return A.hasAttr(IRP, AKs: {ImpliedAttributeKind}, IgnoreSubsumingPositions,
3215	ImpliedAttributeKind);
3216	}
3217
3218	/// See AbstractAttribute::manifest(...).
3219	ChangeStatus manifest(Attributor &A) override {
3220	if (isa<UndefValue>(this->getIRPosition().getAssociatedValue()))
3221	return ChangeStatus::UNCHANGED;
3222	SmallVector<Attribute, 4> DeducedAttrs;
3223	getDeducedAttributes(A, Ctx&: this->getAnchorValue().getContext(), Attrs&: DeducedAttrs);
3224	if (DeducedAttrs.empty())
3225	return ChangeStatus::UNCHANGED;
3226	return A.manifestAttrs(IRP: this->getIRPosition(), DeducedAttrs);
3227	}
3228
3229	/// Return the kind that identifies the abstract attribute implementation.
3230	Attribute::AttrKind getAttrKind() const { return AK; }
3231
3232	/// Return the deduced attributes in \p Attrs.
3233	virtual void getDeducedAttributes(Attributor &A, LLVMContext &Ctx,
3234	SmallVectorImpl<Attribute> &Attrs) const {
3235	Attrs.emplace_back(Attribute::get(Ctx, getAttrKind()));
3236	}
3237	};
3238
3239	/// Base struct for all "concrete attribute" deductions.
3240	///
3241	/// The abstract attribute is a minimal interface that allows the Attributor to
3242	/// orchestrate the abstract/fixpoint analysis. The design allows to hide away
3243	/// implementation choices made for the subclasses but also to structure their
3244	/// implementation and simplify the use of other abstract attributes in-flight.
3245	///
3246	/// To allow easy creation of new attributes, most methods have default
3247	/// implementations. The ones that do not are generally straight forward, except
3248	/// `AbstractAttribute::updateImpl` which is the location of most reasoning
3249	/// associated with the abstract attribute. The update is invoked by the
3250	/// Attributor in case the situation used to justify the current optimistic
3251	/// state might have changed. The Attributor determines this automatically
3252	/// by monitoring the `Attributor::getAAFor` calls made by abstract attributes.
3253	///
3254	/// The `updateImpl` method should inspect the IR and other abstract attributes
3255	/// in-flight to justify the best possible (=optimistic) state. The actual
3256	/// implementation is, similar to the underlying abstract state encoding, not
3257	/// exposed. In the most common case, the `updateImpl` will go through a list of
3258	/// reasons why its optimistic state is valid given the current information. If
3259	/// any combination of them holds and is sufficient to justify the current
3260	/// optimistic state, the method shall return UNCHAGED. If not, the optimistic
3261	/// state is adjusted to the situation and the method shall return CHANGED.
3262	///
3263	/// If the manifestation of the "concrete attribute" deduced by the subclass
3264	/// differs from the "default" behavior, which is a (set of) LLVM-IR
3265	/// attribute(s) for an argument, call site argument, function return value, or
3266	/// function, the `AbstractAttribute::manifest` method should be overloaded.
3267	///
3268	/// NOTE: If the state obtained via getState() is INVALID, thus if
3269	/// AbstractAttribute::getState().isValidState() returns false, no
3270	/// information provided by the methods of this class should be used.
3271	/// NOTE: The Attributor currently has certain limitations to what we can do.
3272	/// As a general rule of thumb, "concrete" abstract attributes should *for
3273	/// now* only perform "backward" information propagation. That means
3274	/// optimistic information obtained through abstract attributes should
3275	/// only be used at positions that precede the origin of the information
3276	/// with regards to the program flow. More practically, information can
3277	/// *now* be propagated from instructions to their enclosing function, but
3278	/// *not* from call sites to the called function. The mechanisms to allow
3279	/// both directions will be added in the future.
3280	/// NOTE: The mechanics of adding a new "concrete" abstract attribute are
3281	/// described in the file comment.
3282	struct AbstractAttribute : public IRPosition, public AADepGraphNode {
3283	using StateType = AbstractState;
3284
3285	AbstractAttribute(const IRPosition &IRP) : IRPosition(IRP) {}
3286
3287	/// Virtual destructor.
3288	virtual ~AbstractAttribute() = default;
3289
3290	/// Compile time access to the IR attribute kind.
3291	static constexpr Attribute::AttrKind IRAttributeKind = Attribute::None;
3292
3293	/// This function is used to identify if an \p DGN is of type
3294	/// AbstractAttribute so that the dyn_cast and cast can use such information
3295	/// to cast an AADepGraphNode to an AbstractAttribute.
3296	///
3297	/// We eagerly return true here because all AADepGraphNodes except for the
3298	/// Synthethis Node are of type AbstractAttribute
3299	static bool classof(const AADepGraphNode *DGN) { return true; }
3300
3301	/// Return false if this AA does anything non-trivial (hence not done by
3302	/// default) in its initializer.
3303	static bool hasTrivialInitializer() { return false; }
3304
3305	/// Return true if this AA requires a "callee" (or an associted function) for
3306	/// a call site positon. Default is optimistic to minimize AAs.
3307	static bool requiresCalleeForCallBase() { return false; }
3308
3309	/// Return true if this AA requires non-asm "callee" for a call site positon.
3310	static bool requiresNonAsmForCallBase() { return true; }
3311
3312	/// Return true if this AA requires all callees for an argument or function
3313	/// positon.
3314	static bool requiresCallersForArgOrFunction() { return false; }
3315
3316	/// Return false if an AA should not be created for \p IRP.
3317	static bool isValidIRPositionForInit(Attributor &A, const IRPosition &IRP) {
3318	return true;
3319	}
3320
3321	/// Return false if an AA should not be updated for \p IRP.
3322	static bool isValidIRPositionForUpdate(Attributor &A, const IRPosition &IRP) {
3323	Function *AssociatedFn = IRP.getAssociatedFunction();
3324	bool IsFnInterface = IRP.isFnInterfaceKind();
3325	assert((!IsFnInterface || AssociatedFn) &&
3326	"Function interface without a function?");
3327
3328	// TODO: Not all attributes require an exact definition. Find a way to
3329	// enable deduction for some but not all attributes in case the
3330	// definition might be changed at runtime, see also
3331	// http://lists.llvm.org/pipermail/llvm-dev/2018-February/121275.html.
3332	// TODO: We could always determine abstract attributes and if sufficient
3333	// information was found we could duplicate the functions that do not
3334	// have an exact definition.
3335	return !IsFnInterface || A.isFunctionIPOAmendable(F: *AssociatedFn);
3336	}
3337
3338	/// Initialize the state with the information in the Attributor \p A.
3339	///
3340	/// This function is called by the Attributor once all abstract attributes
3341	/// have been identified. It can and shall be used for task like:
3342	/// - identify existing knowledge in the IR and use it for the "known state"
3343	/// - perform any work that is not going to change over time, e.g., determine
3344	/// a subset of the IR, or attributes in-flight, that have to be looked at
3345	/// in the `updateImpl` method.
3346	virtual void initialize(Attributor &A) {}
3347
3348	/// A query AA is always scheduled as long as we do updates because it does
3349	/// lazy computation that cannot be determined to be done from the outside.
3350	/// However, while query AAs will not be fixed if they do not have outstanding
3351	/// dependences, we will only schedule them like other AAs. If a query AA that
3352	/// received a new query it needs to request an update via
3353	/// `Attributor::requestUpdateForAA`.
3354	virtual bool isQueryAA() const { return false; }
3355
3356	/// Return the internal abstract state for inspection.
3357	virtual StateType &getState() = 0;
3358	virtual const StateType &getState() const = 0;
3359
3360	/// Return an IR position, see struct IRPosition.
3361	const IRPosition &getIRPosition() const { return *this; };
3362	IRPosition &getIRPosition() { return *this; };
3363
3364	/// Helper functions, for debug purposes only.
3365	///{
3366	void print(raw_ostream &OS) const { print(nullptr, OS); }
3367	void print(Attributor *, raw_ostream &OS) const override;
3368	virtual void printWithDeps(raw_ostream &OS) const;
3369	void dump() const { this->print(OS&: dbgs()); }
3370
3371	/// This function should return the "summarized" assumed state as string.
3372	virtual const std::string getAsStr(Attributor *A) const = 0;
3373
3374	/// This function should return the name of the AbstractAttribute
3375	virtual const std::string getName() const = 0;
3376
3377	/// This function should return the address of the ID of the AbstractAttribute
3378	virtual const char *getIdAddr() const = 0;
3379	///}
3380
3381	/// Allow the Attributor access to the protected methods.
3382	friend struct Attributor;
3383
3384	protected:
3385	/// Hook for the Attributor to trigger an update of the internal state.
3386	///
3387	/// If this attribute is already fixed, this method will return UNCHANGED,
3388	/// otherwise it delegates to `AbstractAttribute::updateImpl`.
3389	///
3390	/// \Return CHANGED if the internal state changed, otherwise UNCHANGED.
3391	ChangeStatus update(Attributor &A);
3392
3393	/// Hook for the Attributor to trigger the manifestation of the information
3394	/// represented by the abstract attribute in the LLVM-IR.
3395	///
3396	/// \Return CHANGED if the IR was altered, otherwise UNCHANGED.
3397	virtual ChangeStatus manifest(Attributor &A) {
3398	return ChangeStatus::UNCHANGED;
3399	}
3400
3401	/// Hook to enable custom statistic tracking, called after manifest that
3402	/// resulted in a change if statistics are enabled.
3403	///
3404	/// We require subclasses to provide an implementation so we remember to
3405	/// add statistics for them.
3406	virtual void trackStatistics() const = 0;
3407
3408	/// The actual update/transfer function which has to be implemented by the
3409	/// derived classes.
3410	///
3411	/// If it is called, the environment has changed and we have to determine if
3412	/// the current information is still valid or adjust it otherwise.
3413	///
3414	/// \Return CHANGED if the internal state changed, otherwise UNCHANGED.
3415	virtual ChangeStatus updateImpl(Attributor &A) = 0;
3416	};
3417
3418	/// Forward declarations of output streams for debug purposes.
3419	///
3420	///{
3421	raw_ostream &operator<<(raw_ostream &OS, const AbstractAttribute &AA);
3422	raw_ostream &operator<<(raw_ostream &OS, ChangeStatus S);
3423	raw_ostream &operator<<(raw_ostream &OS, IRPosition::Kind);
3424	raw_ostream &operator<<(raw_ostream &OS, const IRPosition &);
3425	raw_ostream &operator<<(raw_ostream &OS, const AbstractState &State);
3426	template <typename base_ty, base_ty BestState, base_ty WorstState>
3427	raw_ostream &
3428	operator<<(raw_ostream &OS,
3429	const IntegerStateBase<base_ty, BestState, WorstState> &S) {
3430	return OS << "(" << S.getKnown() << "-" << S.getAssumed() << ")"
3431	<< static_cast<const AbstractState &>(S);
3432	}
3433	raw_ostream &operator<<(raw_ostream &OS, const IntegerRangeState &State);
3434	///}
3435
3436	struct AttributorPass : public PassInfoMixin<AttributorPass> {
3437	PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM);
3438	};
3439	struct AttributorCGSCCPass : public PassInfoMixin<AttributorCGSCCPass> {
3440	PreservedAnalyses run(LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM,
3441	LazyCallGraph &CG, CGSCCUpdateResult &UR);
3442	};
3443
3444	/// A more lightweight version of the Attributor which only runs attribute
3445	/// inference but no simplifications.
3446	struct AttributorLightPass : public PassInfoMixin<AttributorLightPass> {
3447	PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM);
3448	};
3449
3450	/// A more lightweight version of the Attributor which only runs attribute
3451	/// inference but no simplifications.
3452	struct AttributorLightCGSCCPass
3453	: public PassInfoMixin<AttributorLightCGSCCPass> {
3454	PreservedAnalyses run(LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM,
3455	LazyCallGraph &CG, CGSCCUpdateResult &UR);
3456	};
3457
3458	/// Helper function to clamp a state \p S of type \p StateType with the
3459	/// information in \p R and indicate/return if \p S did change (as-in update is
3460	/// required to be run again).
3461	template <typename StateType>
3462	ChangeStatus clampStateAndIndicateChange(StateType &S, const StateType &R) {
3463	auto Assumed = S.getAssumed();
3464	S ^= R;
3465	return Assumed == S.getAssumed() ? ChangeStatus::UNCHANGED
3466	: ChangeStatus::CHANGED;
3467	}
3468
3469	/// ----------------------------------------------------------------------------
3470	/// Abstract Attribute Classes
3471	/// ----------------------------------------------------------------------------
3472
3473	struct AANoUnwind
3474	: public IRAttribute<Attribute::NoUnwind,
3475	StateWrapper<BooleanState, AbstractAttribute>,
3476	AANoUnwind> {
3477	AANoUnwind(const IRPosition &IRP, Attributor &A) : IRAttribute(IRP) {}
3478
3479	/// Returns true if nounwind is assumed.
3480	bool isAssumedNoUnwind() const { return getAssumed(); }
3481
3482	/// Returns true if nounwind is known.
3483	bool isKnownNoUnwind() const { return getKnown(); }
3484
3485	/// Create an abstract attribute view for the position \p IRP.
3486	static AANoUnwind &createForPosition(const IRPosition &IRP, Attributor &A);
3487
3488	/// See AbstractAttribute::getName()
3489	const std::string getName() const override { return "AANoUnwind"; }
3490
3491	/// See AbstractAttribute::getIdAddr()
3492	const char *getIdAddr() const override { return &ID; }
3493
3494	/// This function should return true if the type of the \p AA is AANoUnwind
3495	static bool classof(const AbstractAttribute *AA) {
3496	return (AA->getIdAddr() == &ID);
3497	}
3498
3499	/// Unique ID (due to the unique address)
3500	static const char ID;
3501	};
3502
3503	struct AANoSync
3504	: public IRAttribute<Attribute::NoSync,
3505	StateWrapper<BooleanState, AbstractAttribute>,
3506	AANoSync> {
3507	AANoSync(const IRPosition &IRP, Attributor &A) : IRAttribute(IRP) {}
3508
3509	static bool isImpliedByIR(Attributor &A, const IRPosition &IRP,
3510	Attribute::AttrKind ImpliedAttributeKind,
3511	bool IgnoreSubsumingPositions = false) {
3512	// Note: This is also run for non-IPO amendable functions.
3513	assert(ImpliedAttributeKind == Attribute::NoSync);
3514	if (A.hasAttr(IRP, {Attribute::NoSync}, IgnoreSubsumingPositions,
3515	Attribute::NoSync))
3516	return true;
3517
3518	// Check for readonly + non-convergent.
3519	// TODO: We should be able to use hasAttr for Attributes, not only
3520	// AttrKinds.
3521	Function *F = IRP.getAssociatedFunction();
3522	if (!F || F->isConvergent())
3523	return false;
3524
3525	SmallVector<Attribute, 2> Attrs;
3526	A.getAttrs(IRP, {Attribute::Memory}, Attrs, IgnoreSubsumingPositions);
3527
3528	MemoryEffects ME = MemoryEffects::unknown();
3529	for (const Attribute &Attr : Attrs)
3530	ME &= Attr.getMemoryEffects();
3531
3532	if (!ME.onlyReadsMemory())
3533	return false;
3534
3535	A.manifestAttrs(IRP, DeducedAttrs: Attribute::get(F->getContext(), Attribute::NoSync));
3536	return true;
3537	}
3538
3539	/// See AbstractAttribute::isValidIRPositionForInit
3540	static bool isValidIRPositionForInit(Attributor &A, const IRPosition &IRP) {
3541	if (!IRP.isFunctionScope() &&
3542	!IRP.getAssociatedType()->isPtrOrPtrVectorTy())
3543	return false;
3544	return IRAttribute::isValidIRPositionForInit(A, IRP);
3545	}
3546
3547	/// Returns true if "nosync" is assumed.
3548	bool isAssumedNoSync() const { return getAssumed(); }
3549
3550	/// Returns true if "nosync" is known.
3551	bool isKnownNoSync() const { return getKnown(); }
3552
3553	/// Helper function used to determine whether an instruction is non-relaxed
3554	/// atomic. In other words, if an atomic instruction does not have unordered
3555	/// or monotonic ordering
3556	static bool isNonRelaxedAtomic(const Instruction *I);
3557
3558	/// Helper function specific for intrinsics which are potentially volatile.
3559	static bool isNoSyncIntrinsic(const Instruction *I);
3560
3561	/// Helper function to determine if \p CB is an aligned (GPU) barrier. Aligned
3562	/// barriers have to be executed by all threads. The flag \p ExecutedAligned
3563	/// indicates if the call is executed by all threads in a (thread) block in an
3564	/// aligned way. If that is the case, non-aligned barriers are effectively
3565	/// aligned barriers.
3566	static bool isAlignedBarrier(const CallBase &CB, bool ExecutedAligned);
3567
3568	/// Create an abstract attribute view for the position \p IRP.
3569	static AANoSync &createForPosition(const IRPosition &IRP, Attributor &A);
3570
3571	/// See AbstractAttribute::getName()
3572	const std::string getName() const override { return "AANoSync"; }
3573
3574	/// See AbstractAttribute::getIdAddr()
3575	const char *getIdAddr() const override { return &ID; }
3576
3577	/// This function should return true if the type of the \p AA is AANoSync
3578	static bool classof(const AbstractAttribute *AA) {
3579	return (AA->getIdAddr() == &ID);
3580	}
3581
3582	/// Unique ID (due to the unique address)
3583	static const char ID;
3584	};
3585
3586	/// An abstract interface for all nonnull attributes.
3587	struct AAMustProgress
3588	: public IRAttribute<Attribute::MustProgress,
3589	StateWrapper<BooleanState, AbstractAttribute>,
3590	AAMustProgress> {
3591	AAMustProgress(const IRPosition &IRP, Attributor &A) : IRAttribute(IRP) {}
3592
3593	static bool isImpliedByIR(Attributor &A, const IRPosition &IRP,
3594	Attribute::AttrKind ImpliedAttributeKind,
3595	bool IgnoreSubsumingPositions = false) {
3596	// Note: This is also run for non-IPO amendable functions.
3597	assert(ImpliedAttributeKind == Attribute::MustProgress);
3598	return A.hasAttr(IRP, {Attribute::MustProgress, Attribute::WillReturn},
3599	IgnoreSubsumingPositions, Attribute::MustProgress);
3600	}
3601
3602	/// Return true if we assume that the underlying value is nonnull.
3603	bool isAssumedMustProgress() const { return getAssumed(); }
3604
3605	/// Return true if we know that underlying value is nonnull.
3606	bool isKnownMustProgress() const { return getKnown(); }
3607
3608	/// Create an abstract attribute view for the position \p IRP.
3609	static AAMustProgress &createForPosition(const IRPosition &IRP,
3610	Attributor &A);
3611
3612	/// See AbstractAttribute::getName()
3613	const std::string getName() const override { return "AAMustProgress"; }
3614
3615	/// See AbstractAttribute::getIdAddr()
3616	const char *getIdAddr() const override { return &ID; }
3617
3618	/// This function should return true if the type of the \p AA is
3619	/// AAMustProgress
3620	static bool classof(const AbstractAttribute *AA) {
3621	return (AA->getIdAddr() == &ID);
3622	}
3623
3624	/// Unique ID (due to the unique address)
3625	static const char ID;
3626	};
3627
3628	/// An abstract interface for all nonnull attributes.
3629	struct AANonNull
3630	: public IRAttribute<Attribute::NonNull,
3631	StateWrapper<BooleanState, AbstractAttribute>,
3632	AANonNull> {
3633	AANonNull(const IRPosition &IRP, Attributor &A) : IRAttribute(IRP) {}
3634
3635	/// See AbstractAttribute::hasTrivialInitializer.
3636	static bool hasTrivialInitializer() { return false; }
3637
3638	/// See IRAttribute::isImpliedByUndef.
3639	/// Undef is not necessarily nonnull as nonnull + noundef would cause poison.
3640	/// Poison implies nonnull though.
3641	static bool isImpliedByUndef() { return false; }
3642
3643	/// See AbstractAttribute::isValidIRPositionForInit
3644	static bool isValidIRPositionForInit(Attributor &A, const IRPosition &IRP) {
3645	if (!IRP.getAssociatedType()->isPtrOrPtrVectorTy())
3646	return false;
3647	return IRAttribute::isValidIRPositionForInit(A, IRP);
3648	}
3649
3650	/// See AbstractAttribute::isImpliedByIR(...).
3651	static bool isImpliedByIR(Attributor &A, const IRPosition &IRP,
3652	Attribute::AttrKind ImpliedAttributeKind,
3653	bool IgnoreSubsumingPositions = false);
3654
3655	/// Return true if we assume that the underlying value is nonnull.
3656	bool isAssumedNonNull() const { return getAssumed(); }
3657
3658	/// Return true if we know that underlying value is nonnull.
3659	bool isKnownNonNull() const { return getKnown(); }
3660
3661	/// Create an abstract attribute view for the position \p IRP.
3662	static AANonNull &createForPosition(const IRPosition &IRP, Attributor &A);
3663
3664	/// See AbstractAttribute::getName()
3665	const std::string getName() const override { return "AANonNull"; }
3666
3667	/// See AbstractAttribute::getIdAddr()
3668	const char *getIdAddr() const override { return &ID; }
3669
3670	/// This function should return true if the type of the \p AA is AANonNull
3671	static bool classof(const AbstractAttribute *AA) {
3672	return (AA->getIdAddr() == &ID);
3673	}
3674
3675	/// Unique ID (due to the unique address)
3676	static const char ID;
3677	};
3678
3679	/// An abstract attribute for norecurse.
3680	struct AANoRecurse
3681	: public IRAttribute<Attribute::NoRecurse,
3682	StateWrapper<BooleanState, AbstractAttribute>,
3683	AANoRecurse> {
3684	AANoRecurse(const IRPosition &IRP, Attributor &A) : IRAttribute(IRP) {}
3685
3686	/// Return true if "norecurse" is assumed.
3687	bool isAssumedNoRecurse() const { return getAssumed(); }
3688
3689	/// Return true if "norecurse" is known.
3690	bool isKnownNoRecurse() const { return getKnown(); }
3691
3692	/// Create an abstract attribute view for the position \p IRP.
3693	static AANoRecurse &createForPosition(const IRPosition &IRP, Attributor &A);
3694
3695	/// See AbstractAttribute::getName()
3696	const std::string getName() const override { return "AANoRecurse"; }
3697
3698	/// See AbstractAttribute::getIdAddr()
3699	const char *getIdAddr() const override { return &ID; }
3700
3701	/// This function should return true if the type of the \p AA is AANoRecurse
3702	static bool classof(const AbstractAttribute *AA) {
3703	return (AA->getIdAddr() == &ID);
3704	}
3705
3706	/// Unique ID (due to the unique address)
3707	static const char ID;
3708	};
3709
3710	/// An abstract attribute for willreturn.
3711	struct AAWillReturn
3712	: public IRAttribute<Attribute::WillReturn,
3713	StateWrapper<BooleanState, AbstractAttribute>,
3714	AAWillReturn> {
3715	AAWillReturn(const IRPosition &IRP, Attributor &A) : IRAttribute(IRP) {}
3716
3717	static bool isImpliedByIR(Attributor &A, const IRPosition &IRP,
3718	Attribute::AttrKind ImpliedAttributeKind,
3719	bool IgnoreSubsumingPositions = false) {
3720	// Note: This is also run for non-IPO amendable functions.
3721	assert(ImpliedAttributeKind == Attribute::WillReturn);
3722	if (IRAttribute::isImpliedByIR(A, IRP, ImpliedAttributeKind,
3723	IgnoreSubsumingPositions))
3724	return true;
3725	if (!isImpliedByMustprogressAndReadonly(A, IRP))
3726	return false;
3727	A.manifestAttrs(IRP, DeducedAttrs: Attribute::get(IRP.getAnchorValue().getContext(),
3728	Attribute::WillReturn));
3729	return true;
3730	}
3731
3732	/// Check for `mustprogress` and `readonly` as they imply `willreturn`.
3733	static bool isImpliedByMustprogressAndReadonly(Attributor &A,
3734	const IRPosition &IRP) {
3735	// Check for `mustprogress` in the scope and the associated function which
3736	// might be different if this is a call site.
3737	if (!A.hasAttr(IRP, {Attribute::MustProgress}))
3738	return false;
3739
3740	SmallVector<Attribute, 2> Attrs;
3741	A.getAttrs(IRP, {Attribute::Memory}, Attrs,
3742	/* IgnoreSubsumingPositions */ false);
3743
3744	MemoryEffects ME = MemoryEffects::unknown();
3745	for (const Attribute &Attr : Attrs)
3746	ME &= Attr.getMemoryEffects();
3747	return ME.onlyReadsMemory();
3748	}
3749
3750	/// Return true if "willreturn" is assumed.
3751	bool isAssumedWillReturn() const { return getAssumed(); }
3752
3753	/// Return true if "willreturn" is known.
3754	bool isKnownWillReturn() const { return getKnown(); }
3755
3756	/// Create an abstract attribute view for the position \p IRP.
3757	static AAWillReturn &createForPosition(const IRPosition &IRP, Attributor &A);
3758
3759	/// See AbstractAttribute::getName()
3760	const std::string getName() const override { return "AAWillReturn"; }
3761
3762	/// See AbstractAttribute::getIdAddr()
3763	const char *getIdAddr() const override { return &ID; }
3764
3765	/// This function should return true if the type of the \p AA is AAWillReturn
3766	static bool classof(const AbstractAttribute *AA) {
3767	return (AA->getIdAddr() == &ID);
3768	}
3769
3770	/// Unique ID (due to the unique address)
3771	static const char ID;
3772	};
3773
3774	/// An abstract attribute for undefined behavior.
3775	struct AAUndefinedBehavior
3776	: public StateWrapper<BooleanState, AbstractAttribute> {
3777	using Base = StateWrapper<BooleanState, AbstractAttribute>;
3778	AAUndefinedBehavior(const IRPosition &IRP, Attributor &A) : Base(IRP) {}
3779
3780	/// Return true if "undefined behavior" is assumed.
3781	bool isAssumedToCauseUB() const { return getAssumed(); }
3782
3783	/// Return true if "undefined behavior" is assumed for a specific instruction.
3784	virtual bool isAssumedToCauseUB(Instruction *I) const = 0;
3785
3786	/// Return true if "undefined behavior" is known.
3787	bool isKnownToCauseUB() const { return getKnown(); }
3788
3789	/// Return true if "undefined behavior" is known for a specific instruction.
3790	virtual bool isKnownToCauseUB(Instruction *I) const = 0;
3791
3792	/// Create an abstract attribute view for the position \p IRP.
3793	static AAUndefinedBehavior &createForPosition(const IRPosition &IRP,
3794	Attributor &A);
3795
3796	/// See AbstractAttribute::getName()
3797	const std::string getName() const override { return "AAUndefinedBehavior"; }
3798
3799	/// See AbstractAttribute::getIdAddr()
3800	const char *getIdAddr() const override { return &ID; }
3801
3802	/// This function should return true if the type of the \p AA is
3803	/// AAUndefineBehavior
3804	static bool classof(const AbstractAttribute *AA) {
3805	return (AA->getIdAddr() == &ID);
3806	}
3807
3808	/// Unique ID (due to the unique address)
3809	static const char ID;
3810	};
3811
3812	/// An abstract interface to determine reachability of point A to B.
3813	struct AAIntraFnReachability
3814	: public StateWrapper<BooleanState, AbstractAttribute> {
3815	using Base = StateWrapper<BooleanState, AbstractAttribute>;
3816	AAIntraFnReachability(const IRPosition &IRP, Attributor &A) : Base(IRP) {}
3817
3818	/// Returns true if 'From' instruction is assumed to reach, 'To' instruction.
3819	/// Users should provide two positions they are interested in, and the class
3820	/// determines (and caches) reachability.
3821	virtual bool isAssumedReachable(
3822	Attributor &A, const Instruction &From, const Instruction &To,
3823	const AA::InstExclusionSetTy *ExclusionSet = nullptr) const = 0;
3824
3825	/// Create an abstract attribute view for the position \p IRP.
3826	static AAIntraFnReachability &createForPosition(const IRPosition &IRP,
3827	Attributor &A);
3828
3829	/// See AbstractAttribute::getName()
3830	const std::string getName() const override { return "AAIntraFnReachability"; }
3831
3832	/// See AbstractAttribute::getIdAddr()
3833	const char *getIdAddr() const override { return &ID; }
3834
3835	/// This function should return true if the type of the \p AA is
3836	/// AAIntraFnReachability
3837	static bool classof(const AbstractAttribute *AA) {
3838	return (AA->getIdAddr() == &ID);
3839	}
3840
3841	/// Unique ID (due to the unique address)
3842	static const char ID;
3843	};
3844
3845	/// An abstract interface for all noalias attributes.
3846	struct AANoAlias
3847	: public IRAttribute<Attribute::NoAlias,
3848	StateWrapper<BooleanState, AbstractAttribute>,
3849	AANoAlias> {
3850	AANoAlias(const IRPosition &IRP, Attributor &A) : IRAttribute(IRP) {}
3851
3852	/// See AbstractAttribute::isValidIRPositionForInit
3853	static bool isValidIRPositionForInit(Attributor &A, const IRPosition &IRP) {
3854	if (!IRP.getAssociatedType()->isPtrOrPtrVectorTy())
3855	return false;
3856	return IRAttribute::isValidIRPositionForInit(A, IRP);
3857	}
3858
3859	/// See IRAttribute::isImpliedByIR
3860	static bool isImpliedByIR(Attributor &A, const IRPosition &IRP,
3861	Attribute::AttrKind ImpliedAttributeKind,
3862	bool IgnoreSubsumingPositions = false);
3863
3864	/// See AbstractAttribute::requiresCallersForArgOrFunction
3865	static bool requiresCallersForArgOrFunction() { return true; }
3866
3867	/// Return true if we assume that the underlying value is alias.
3868	bool isAssumedNoAlias() const { return getAssumed(); }
3869
3870	/// Return true if we know that underlying value is noalias.
3871	bool isKnownNoAlias() const { return getKnown(); }
3872
3873	/// Create an abstract attribute view for the position \p IRP.
3874	static AANoAlias &createForPosition(const IRPosition &IRP, Attributor &A);
3875
3876	/// See AbstractAttribute::getName()
3877	const std::string getName() const override { return "AANoAlias"; }
3878
3879	/// See AbstractAttribute::getIdAddr()
3880	const char *getIdAddr() const override { return &ID; }
3881
3882	/// This function should return true if the type of the \p AA is AANoAlias
3883	static bool classof(const AbstractAttribute *AA) {
3884	return (AA->getIdAddr() == &ID);
3885	}
3886
3887	/// Unique ID (due to the unique address)
3888	static const char ID;
3889	};
3890
3891	/// An AbstractAttribute for nofree.
3892	struct AANoFree
3893	: public IRAttribute<Attribute::NoFree,
3894	StateWrapper<BooleanState, AbstractAttribute>,
3895	AANoFree> {
3896	AANoFree(const IRPosition &IRP, Attributor &A) : IRAttribute(IRP) {}
3897
3898	/// See IRAttribute::isImpliedByIR
3899	static bool isImpliedByIR(Attributor &A, const IRPosition &IRP,
3900	Attribute::AttrKind ImpliedAttributeKind,
3901	bool IgnoreSubsumingPositions = false) {
3902	// Note: This is also run for non-IPO amendable functions.
3903	assert(ImpliedAttributeKind == Attribute::NoFree);
3904	return A.hasAttr(
3905	IRP, {Attribute::ReadNone, Attribute::ReadOnly, Attribute::NoFree},
3906	IgnoreSubsumingPositions, Attribute::NoFree);
3907	}
3908
3909	/// See AbstractAttribute::isValidIRPositionForInit
3910	static bool isValidIRPositionForInit(Attributor &A, const IRPosition &IRP) {
3911	if (!IRP.isFunctionScope() &&
3912	!IRP.getAssociatedType()->isPtrOrPtrVectorTy())
3913	return false;
3914	return IRAttribute::isValidIRPositionForInit(A, IRP);
3915	}
3916
3917	/// Return true if "nofree" is assumed.
3918	bool isAssumedNoFree() const { return getAssumed(); }
3919
3920	/// Return true if "nofree" is known.
3921	bool isKnownNoFree() const { return getKnown(); }
3922
3923	/// Create an abstract attribute view for the position \p IRP.
3924	static AANoFree &createForPosition(const IRPosition &IRP, Attributor &A);
3925
3926	/// See AbstractAttribute::getName()
3927	const std::string getName() const override { return "AANoFree"; }
3928
3929	/// See AbstractAttribute::getIdAddr()
3930	const char *getIdAddr() const override { return &ID; }
3931
3932	/// This function should return true if the type of the \p AA is AANoFree
3933	static bool classof(const AbstractAttribute *AA) {
3934	return (AA->getIdAddr() == &ID);
3935	}
3936
3937	/// Unique ID (due to the unique address)
3938	static const char ID;
3939	};
3940
3941	/// An AbstractAttribute for noreturn.
3942	struct AANoReturn
3943	: public IRAttribute<Attribute::NoReturn,
3944	StateWrapper<BooleanState, AbstractAttribute>,
3945	AANoReturn> {
3946	AANoReturn(const IRPosition &IRP, Attributor &A) : IRAttribute(IRP) {}
3947
3948	/// Return true if the underlying object is assumed to never return.
3949	bool isAssumedNoReturn() const { return getAssumed(); }
3950
3951	/// Return true if the underlying object is known to never return.
3952	bool isKnownNoReturn() const { return getKnown(); }
3953
3954	/// Create an abstract attribute view for the position \p IRP.
3955	static AANoReturn &createForPosition(const IRPosition &IRP, Attributor &A);
3956
3957	/// See AbstractAttribute::getName()
3958	const std::string getName() const override { return "AANoReturn"; }
3959
3960	/// See AbstractAttribute::getIdAddr()
3961	const char *getIdAddr() const override { return &ID; }
3962
3963	/// This function should return true if the type of the \p AA is AANoReturn
3964	static bool classof(const AbstractAttribute *AA) {
3965	return (AA->getIdAddr() == &ID);
3966	}
3967
3968	/// Unique ID (due to the unique address)
3969	static const char ID;
3970	};
3971
3972	/// An abstract interface for liveness abstract attribute.
3973	struct AAIsDead
3974	: public StateWrapper<BitIntegerState<uint8_t, 3, 0>, AbstractAttribute> {
3975	using Base = StateWrapper<BitIntegerState<uint8_t, 3, 0>, AbstractAttribute>;
3976	AAIsDead(const IRPosition &IRP, Attributor &A) : Base(IRP) {}
3977
3978	/// See AbstractAttribute::isValidIRPositionForInit
3979	static bool isValidIRPositionForInit(Attributor &A, const IRPosition &IRP) {
3980	if (IRP.getPositionKind() == IRPosition::IRP_FUNCTION)
3981	return isa<Function>(Val: IRP.getAnchorValue()) &&
3982	!cast<Function>(Val&: IRP.getAnchorValue()).isDeclaration();
3983	return true;
3984	}
3985
3986	/// State encoding bits. A set bit in the state means the property holds.
3987	enum {
3988	HAS_NO_EFFECT = 1 << 0,
3989	IS_REMOVABLE = 1 << 1,
3990
3991	IS_DEAD = HAS_NO_EFFECT | IS_REMOVABLE,
3992	};
3993	static_assert(IS_DEAD == getBestState(), "Unexpected BEST_STATE value");
3994
3995	protected:
3996	/// The query functions are protected such that other attributes need to go
3997	/// through the Attributor interfaces: `Attributor::isAssumedDead(...)`
3998
3999	/// Returns true if the underlying value is assumed dead.
4000	virtual bool isAssumedDead() const = 0;
4001
4002	/// Returns true if the underlying value is known dead.
4003	virtual bool isKnownDead() const = 0;
4004
4005	/// Returns true if \p BB is known dead.
4006	virtual bool isKnownDead(const BasicBlock *BB) const = 0;
4007
4008	/// Returns true if \p I is assumed dead.
4009	virtual bool isAssumedDead(const Instruction *I) const = 0;
4010
4011	/// Returns true if \p I is known dead.
4012	virtual bool isKnownDead(const Instruction *I) const = 0;
4013
4014	/// Return true if the underlying value is a store that is known to be
4015	/// removable. This is different from dead stores as the removable store
4016	/// can have an effect on live values, especially loads, but that effect
4017	/// is propagated which allows us to remove the store in turn.
4018	virtual bool isRemovableStore() const { return false; }
4019
4020	/// This method is used to check if at least one instruction in a collection
4021	/// of instructions is live.
4022	template <typename T> bool isLiveInstSet(T begin, T end) const {
4023	for (const auto &I : llvm::make_range(begin, end)) {
4024	assert(I->getFunction() == getIRPosition().getAssociatedFunction() &&
4025	"Instruction must be in the same anchor scope function.");
4026
4027	if (!isAssumedDead(I))
4028	return true;
4029	}
4030
4031	return false;
4032	}
4033
4034	public:
4035	/// Create an abstract attribute view for the position \p IRP.
4036	static AAIsDead &createForPosition(const IRPosition &IRP, Attributor &A);
4037
4038	/// Determine if \p F might catch asynchronous exceptions.
4039	static bool mayCatchAsynchronousExceptions(const Function &F) {
4040	return F.hasPersonalityFn() && !canSimplifyInvokeNoUnwind(F: &F);
4041	}
4042
4043	/// Returns true if \p BB is assumed dead.
4044	virtual bool isAssumedDead(const BasicBlock *BB) const = 0;
4045
4046	/// Return if the edge from \p From BB to \p To BB is assumed dead.
4047	/// This is specifically useful in AAReachability.
4048	virtual bool isEdgeDead(const BasicBlock *From, const BasicBlock *To) const {
4049	return false;
4050	}
4051
4052	/// See AbstractAttribute::getName()
4053	const std::string getName() const override { return "AAIsDead"; }
4054
4055	/// See AbstractAttribute::getIdAddr()
4056	const char *getIdAddr() const override { return &ID; }
4057
4058	/// This function should return true if the type of the \p AA is AAIsDead
4059	static bool classof(const AbstractAttribute *AA) {
4060	return (AA->getIdAddr() == &ID);
4061	}
4062
4063	/// Unique ID (due to the unique address)
4064	static const char ID;
4065
4066	friend struct Attributor;
4067	};
4068
4069	/// State for dereferenceable attribute
4070	struct DerefState : AbstractState {
4071
4072	static DerefState getBestState() { return DerefState(); }
4073	static DerefState getBestState(const DerefState &) { return getBestState(); }
4074
4075	/// Return the worst possible representable state.
4076	static DerefState getWorstState() {
4077	DerefState DS;
4078	DS.indicatePessimisticFixpoint();
4079	return DS;
4080	}
4081	static DerefState getWorstState(const DerefState &) {
4082	return getWorstState();
4083	}
4084
4085	/// State representing for dereferenceable bytes.
4086	IncIntegerState<> DerefBytesState;
4087
4088	/// Map representing for accessed memory offsets and sizes.
4089	/// A key is Offset and a value is size.
4090	/// If there is a load/store instruction something like,
4091	/// p[offset] = v;
4092	/// (offset, sizeof(v)) will be inserted to this map.
4093	/// std::map is used because we want to iterate keys in ascending order.
4094	std::map<int64_t, uint64_t> AccessedBytesMap;
4095
4096	/// Helper function to calculate dereferenceable bytes from current known
4097	/// bytes and accessed bytes.
4098	///
4099	/// int f(int *A){
4100	/// *A = 0;
4101	/// *(A+2) = 2;
4102	/// *(A+1) = 1;
4103	/// *(A+10) = 10;
4104	/// }
4105	/// ```
4106	/// In that case, AccessedBytesMap is `{0:4, 4:4, 8:4, 40:4}`.
4107	/// AccessedBytesMap is std::map so it is iterated in accending order on
4108	/// key(Offset). So KnownBytes will be updated like this:
4109	///
4110	/// |Access | KnownBytes
4111	/// |(0, 4)| 0 -> 4
4112	/// |(4, 4)| 4 -> 8
4113	/// |(8, 4)| 8 -> 12
4114	/// |(40, 4) | 12 (break)
4115	void computeKnownDerefBytesFromAccessedMap() {
4116	int64_t KnownBytes = DerefBytesState.getKnown();
4117	for (auto &Access : AccessedBytesMap) {
4118	if (KnownBytes < Access.first)
4119	break;
4120	KnownBytes = std::max(a: KnownBytes, b: Access.first + (int64_t)Access.second);
4121	}
4122
4123	DerefBytesState.takeKnownMaximum(Value: KnownBytes);
4124	}
4125
4126	/// State representing that whether the value is globaly dereferenceable.
4127	BooleanState GlobalState;
4128
4129	/// See AbstractState::isValidState()
4130	bool isValidState() const override { return DerefBytesState.isValidState(); }
4131
4132	/// See AbstractState::isAtFixpoint()
4133	bool isAtFixpoint() const override {
4134	return !isValidState() ||
4135	(DerefBytesState.isAtFixpoint() && GlobalState.isAtFixpoint());
4136	}
4137
4138	/// See AbstractState::indicateOptimisticFixpoint(...)
4139	ChangeStatus indicateOptimisticFixpoint() override {
4140	DerefBytesState.indicateOptimisticFixpoint();
4141	GlobalState.indicateOptimisticFixpoint();
4142	return ChangeStatus::UNCHANGED;
4143	}
4144
4145	/// See AbstractState::indicatePessimisticFixpoint(...)
4146	ChangeStatus indicatePessimisticFixpoint() override {
4147	DerefBytesState.indicatePessimisticFixpoint();
4148	GlobalState.indicatePessimisticFixpoint();
4149	return ChangeStatus::CHANGED;
4150	}
4151
4152	/// Update known dereferenceable bytes.
4153	void takeKnownDerefBytesMaximum(uint64_t Bytes) {
4154	DerefBytesState.takeKnownMaximum(Value: Bytes);
4155
4156	// Known bytes might increase.
4157	computeKnownDerefBytesFromAccessedMap();
4158	}
4159
4160	/// Update assumed dereferenceable bytes.
4161	void takeAssumedDerefBytesMinimum(uint64_t Bytes) {
4162	DerefBytesState.takeAssumedMinimum(Value: Bytes);
4163	}
4164
4165	/// Add accessed bytes to the map.
4166	void addAccessedBytes(int64_t Offset, uint64_t Size) {
4167	uint64_t &AccessedBytes = AccessedBytesMap[Offset];
4168	AccessedBytes = std::max(a: AccessedBytes, b: Size);
4169
4170	// Known bytes might increase.
4171	computeKnownDerefBytesFromAccessedMap();
4172	}
4173
4174	/// Equality for DerefState.
4175	bool operator==(const DerefState &R) const {
4176	return this->DerefBytesState == R.DerefBytesState &&
4177	this->GlobalState == R.GlobalState;
4178	}
4179
4180	/// Inequality for DerefState.
4181	bool operator!=(const DerefState &R) const { return !(*this == R); }
4182
4183	/// See IntegerStateBase::operator^=
4184	DerefState operator^=(const DerefState &R) {
4185	DerefBytesState ^= R.DerefBytesState;
4186	GlobalState ^= R.GlobalState;
4187	return *this;
4188	}
4189
4190	/// See IntegerStateBase::operator+=
4191	DerefState operator+=(const DerefState &R) {
4192	DerefBytesState += R.DerefBytesState;
4193	GlobalState += R.GlobalState;
4194	return *this;
4195	}
4196
4197	/// See IntegerStateBase::operator&=
4198	DerefState operator&=(const DerefState &R) {
4199	DerefBytesState &= R.DerefBytesState;
4200	GlobalState &= R.GlobalState;
4201	return *this;
4202	}
4203
4204	/// See IntegerStateBase::operator|=
4205	DerefState operator|=(const DerefState &R) {
4206	DerefBytesState |= R.DerefBytesState;
4207	GlobalState |= R.GlobalState;
4208	return *this;
4209	}
4210	};
4211
4212	/// An abstract interface for all dereferenceable attribute.
4213	struct AADereferenceable
4214	: public IRAttribute<Attribute::Dereferenceable,
4215	StateWrapper<DerefState, AbstractAttribute>,
4216	AADereferenceable> {
4217	AADereferenceable(const IRPosition &IRP, Attributor &A) : IRAttribute(IRP) {}
4218
4219	/// See AbstractAttribute::isValidIRPositionForInit
4220	static bool isValidIRPositionForInit(Attributor &A, const IRPosition &IRP) {
4221	if (!IRP.getAssociatedType()->isPtrOrPtrVectorTy())
4222	return false;
4223	return IRAttribute::isValidIRPositionForInit(A, IRP);
4224	}
4225
4226	/// Return true if we assume that underlying value is
4227	/// dereferenceable(_or_null) globally.
4228	bool isAssumedGlobal() const { return GlobalState.getAssumed(); }
4229
4230	/// Return true if we know that underlying value is
4231	/// dereferenceable(_or_null) globally.
4232	bool isKnownGlobal() const { return GlobalState.getKnown(); }
4233
4234	/// Return assumed dereferenceable bytes.
4235	uint32_t getAssumedDereferenceableBytes() const {
4236	return DerefBytesState.getAssumed();
4237	}
4238
4239	/// Return known dereferenceable bytes.
4240	uint32_t getKnownDereferenceableBytes() const {
4241	return DerefBytesState.getKnown();
4242	}
4243
4244	/// Create an abstract attribute view for the position \p IRP.
4245	static AADereferenceable &createForPosition(const IRPosition &IRP,
4246	Attributor &A);
4247
4248	/// See AbstractAttribute::getName()
4249	const std::string getName() const override { return "AADereferenceable"; }
4250
4251	/// See AbstractAttribute::getIdAddr()
4252	const char *getIdAddr() const override { return &ID; }
4253
4254	/// This function should return true if the type of the \p AA is
4255	/// AADereferenceable
4256	static bool classof(const AbstractAttribute *AA) {
4257	return (AA->getIdAddr() == &ID);
4258	}
4259
4260	/// Unique ID (due to the unique address)
4261	static const char ID;
4262	};
4263
4264	using AAAlignmentStateType =
4265	IncIntegerState<uint64_t, Value::MaximumAlignment, 1>;
4266	/// An abstract interface for all align attributes.
4267	struct AAAlign
4268	: public IRAttribute<Attribute::Alignment,
4269	StateWrapper<AAAlignmentStateType, AbstractAttribute>,
4270	AAAlign> {
4271	AAAlign(const IRPosition &IRP, Attributor &A) : IRAttribute(IRP) {}
4272
4273	/// See AbstractAttribute::isValidIRPositionForInit
4274	static bool isValidIRPositionForInit(Attributor &A, const IRPosition &IRP) {
4275	if (!IRP.getAssociatedType()->isPtrOrPtrVectorTy())
4276	return false;
4277	return IRAttribute::isValidIRPositionForInit(A, IRP);
4278	}
4279
4280	/// Return assumed alignment.
4281	Align getAssumedAlign() const { return Align(getAssumed()); }
4282
4283	/// Return known alignment.
4284	Align getKnownAlign() const { return Align(getKnown()); }
4285
4286	/// See AbstractAttribute::getName()
4287	const std::string getName() const override { return "AAAlign"; }
4288
4289	/// See AbstractAttribute::getIdAddr()
4290	const char *getIdAddr() const override { return &ID; }
4291
4292	/// This function should return true if the type of the \p AA is AAAlign
4293	static bool classof(const AbstractAttribute *AA) {
4294	return (AA->getIdAddr() == &ID);
4295	}
4296
4297	/// Create an abstract attribute view for the position \p IRP.
4298	static AAAlign &createForPosition(const IRPosition &IRP, Attributor &A);
4299
4300	/// Unique ID (due to the unique address)
4301	static const char ID;
4302	};
4303
4304	/// An abstract interface to track if a value leaves it's defining function
4305	/// instance.
4306	/// TODO: We should make it a ternary AA tracking uniqueness, and uniqueness
4307	/// wrt. the Attributor analysis separately.
4308	struct AAInstanceInfo : public StateWrapper<BooleanState, AbstractAttribute> {
4309	AAInstanceInfo(const IRPosition &IRP, Attributor &A)
4310	: StateWrapper<BooleanState, AbstractAttribute>(IRP) {}
4311
4312	/// Return true if we know that the underlying value is unique in its scope
4313	/// wrt. the Attributor analysis. That means it might not be unique but we can
4314	/// still use pointer equality without risking to represent two instances with
4315	/// one `llvm::Value`.
4316	bool isKnownUniqueForAnalysis() const { return isKnown(); }
4317
4318	/// Return true if we assume that the underlying value is unique in its scope
4319	/// wrt. the Attributor analysis. That means it might not be unique but we can
4320	/// still use pointer equality without risking to represent two instances with
4321	/// one `llvm::Value`.
4322	bool isAssumedUniqueForAnalysis() const { return isAssumed(); }
4323
4324	/// Create an abstract attribute view for the position \p IRP.
4325	static AAInstanceInfo &createForPosition(const IRPosition &IRP,
4326	Attributor &A);
4327
4328	/// See AbstractAttribute::getName()
4329	const std::string getName() const override { return "AAInstanceInfo"; }
4330
4331	/// See AbstractAttribute::getIdAddr()
4332	const char *getIdAddr() const override { return &ID; }
4333
4334	/// This function should return true if the type of the \p AA is
4335	/// AAInstanceInfo
4336	static bool classof(const AbstractAttribute *AA) {
4337	return (AA->getIdAddr() == &ID);
4338	}
4339
4340	/// Unique ID (due to the unique address)
4341	static const char ID;
4342	};
4343
4344	/// An abstract interface for all nocapture attributes.
4345	struct AANoCapture
4346	: public IRAttribute<
4347	Attribute::NoCapture,
4348	StateWrapper<BitIntegerState<uint16_t, 7, 0>, AbstractAttribute>,
4349	AANoCapture> {
4350	AANoCapture(const IRPosition &IRP, Attributor &A) : IRAttribute(IRP) {}
4351
4352	/// See IRAttribute::isImpliedByIR
4353	static bool isImpliedByIR(Attributor &A, const IRPosition &IRP,
4354	Attribute::AttrKind ImpliedAttributeKind,
4355	bool IgnoreSubsumingPositions = false);
4356
4357	/// Update \p State according to the capture capabilities of \p F for position
4358	/// \p IRP.
4359	static void determineFunctionCaptureCapabilities(const IRPosition &IRP,
4360	const Function &F,
4361	BitIntegerState &State);
4362
4363	/// See AbstractAttribute::isValidIRPositionForInit
4364	static bool isValidIRPositionForInit(Attributor &A, const IRPosition &IRP) {
4365	if (!IRP.getAssociatedType()->isPtrOrPtrVectorTy())
4366	return false;
4367	return IRAttribute::isValidIRPositionForInit(A, IRP);
4368	}
4369
4370	/// State encoding bits. A set bit in the state means the property holds.
4371	/// NO_CAPTURE is the best possible state, 0 the worst possible state.
4372	enum {
4373	NOT_CAPTURED_IN_MEM = 1 << 0,
4374	NOT_CAPTURED_IN_INT = 1 << 1,
4375	NOT_CAPTURED_IN_RET = 1 << 2,
4376
4377	/// If we do not capture the value in memory or through integers we can only
4378	/// communicate it back as a derived pointer.
4379	NO_CAPTURE_MAYBE_RETURNED = NOT_CAPTURED_IN_MEM | NOT_CAPTURED_IN_INT,
4380
4381	/// If we do not capture the value in memory, through integers, or as a
4382	/// derived pointer we know it is not captured.
4383	NO_CAPTURE =
4384	NOT_CAPTURED_IN_MEM | NOT_CAPTURED_IN_INT | NOT_CAPTURED_IN_RET,
4385	};
4386
4387	/// Return true if we know that the underlying value is not captured in its
4388	/// respective scope.
4389	bool isKnownNoCapture() const { return isKnown(NO_CAPTURE); }
4390
4391	/// Return true if we assume that the underlying value is not captured in its
4392	/// respective scope.
4393	bool isAssumedNoCapture() const { return isAssumed(NO_CAPTURE); }
4394
4395	/// Return true if we know that the underlying value is not captured in its
4396	/// respective scope but we allow it to escape through a "return".
4397	bool isKnownNoCaptureMaybeReturned() const {
4398	return isKnown(NO_CAPTURE_MAYBE_RETURNED);
4399	}
4400
4401	/// Return true if we assume that the underlying value is not captured in its
4402	/// respective scope but we allow it to escape through a "return".
4403	bool isAssumedNoCaptureMaybeReturned() const {
4404	return isAssumed(NO_CAPTURE_MAYBE_RETURNED);
4405	}
4406
4407	/// Create an abstract attribute view for the position \p IRP.
4408	static AANoCapture &createForPosition(const IRPosition &IRP, Attributor &A);
4409
4410	/// See AbstractAttribute::getName()
4411	const std::string getName() const override { return "AANoCapture"; }
4412
4413	/// See AbstractAttribute::getIdAddr()
4414	const char *getIdAddr() const override { return &ID; }
4415
4416	/// This function should return true if the type of the \p AA is AANoCapture
4417	static bool classof(const AbstractAttribute *AA) {
4418	return (AA->getIdAddr() == &ID);
4419	}
4420
4421	/// Unique ID (due to the unique address)
4422	static const char ID;
4423	};
4424
4425	struct ValueSimplifyStateType : public AbstractState {
4426
4427	ValueSimplifyStateType(Type *Ty) : Ty(Ty) {}
4428
4429	static ValueSimplifyStateType getBestState(Type *Ty) {
4430	return ValueSimplifyStateType(Ty);
4431	}
4432	static ValueSimplifyStateType getBestState(const ValueSimplifyStateType &VS) {
4433	return getBestState(Ty: VS.Ty);
4434	}
4435
4436	/// Return the worst possible representable state.
4437	static ValueSimplifyStateType getWorstState(Type *Ty) {
4438	ValueSimplifyStateType DS(Ty);
4439	DS.indicatePessimisticFixpoint();
4440	return DS;
4441	}
4442	static ValueSimplifyStateType
4443	getWorstState(const ValueSimplifyStateType &VS) {
4444	return getWorstState(Ty: VS.Ty);
4445	}
4446
4447	/// See AbstractState::isValidState(...)
4448	bool isValidState() const override { return BS.isValidState(); }
4449
4450	/// See AbstractState::isAtFixpoint(...)
4451	bool isAtFixpoint() const override { return BS.isAtFixpoint(); }
4452
4453	/// Return the assumed state encoding.
4454	ValueSimplifyStateType getAssumed() { return *this; }
4455	const ValueSimplifyStateType &getAssumed() const { return *this; }
4456
4457	/// See AbstractState::indicatePessimisticFixpoint(...)
4458	ChangeStatus indicatePessimisticFixpoint() override {
4459	return BS.indicatePessimisticFixpoint();
4460	}
4461
4462	/// See AbstractState::indicateOptimisticFixpoint(...)
4463	ChangeStatus indicateOptimisticFixpoint() override {
4464	return BS.indicateOptimisticFixpoint();
4465	}
4466
4467	/// "Clamp" this state with \p PVS.
4468	ValueSimplifyStateType operator^=(const ValueSimplifyStateType &VS) {
4469	BS ^= VS.BS;
4470	unionAssumed(Other: VS.SimplifiedAssociatedValue);
4471	return *this;
4472	}
4473
4474	bool operator==(const ValueSimplifyStateType &RHS) const {
4475	if (isValidState() != RHS.isValidState())
4476	return false;
4477	if (!isValidState() && !RHS.isValidState())
4478	return true;
4479	return SimplifiedAssociatedValue == RHS.SimplifiedAssociatedValue;
4480	}
4481
4482	protected:
4483	/// The type of the original value.
4484	Type *Ty;
4485
4486	/// Merge \p Other into the currently assumed simplified value
4487	bool unionAssumed(std::optional<Value *> Other);
4488
4489	/// Helper to track validity and fixpoint
4490	BooleanState BS;
4491
4492	/// An assumed simplified value. Initially, it is set to std::nullopt, which
4493	/// means that the value is not clear under current assumption. If in the
4494	/// pessimistic state, getAssumedSimplifiedValue doesn't return this value but
4495	/// returns orignal associated value.
4496	std::optional<Value *> SimplifiedAssociatedValue;
4497	};
4498
4499	/// An abstract interface for value simplify abstract attribute.
4500	struct AAValueSimplify
4501	: public StateWrapper<ValueSimplifyStateType, AbstractAttribute, Type *> {
4502	using Base = StateWrapper<ValueSimplifyStateType, AbstractAttribute, Type *>;
4503	AAValueSimplify(const IRPosition &IRP, Attributor &A)
4504	: Base(IRP, IRP.getAssociatedType()) {}
4505
4506	/// Create an abstract attribute view for the position \p IRP.
4507	static AAValueSimplify &createForPosition(const IRPosition &IRP,
4508	Attributor &A);
4509
4510	/// See AbstractAttribute::getName()
4511	const std::string getName() const override { return "AAValueSimplify"; }
4512
4513	/// See AbstractAttribute::getIdAddr()
4514	const char *getIdAddr() const override { return &ID; }
4515
4516	/// This function should return true if the type of the \p AA is
4517	/// AAValueSimplify
4518	static bool classof(const AbstractAttribute *AA) {
4519	return (AA->getIdAddr() == &ID);
4520	}
4521
4522	/// Unique ID (due to the unique address)
4523	static const char ID;
4524
4525	private:
4526	/// Return an assumed simplified value if a single candidate is found. If
4527	/// there cannot be one, return original value. If it is not clear yet, return
4528	/// std::nullopt.
4529	///
4530	/// Use `Attributor::getAssumedSimplified` for value simplification.
4531	virtual std::optional<Value *>
4532	getAssumedSimplifiedValue(Attributor &A) const = 0;
4533
4534	friend struct Attributor;
4535	};
4536
4537	struct AAHeapToStack : public StateWrapper<BooleanState, AbstractAttribute> {
4538	using Base = StateWrapper<BooleanState, AbstractAttribute>;
4539	AAHeapToStack(const IRPosition &IRP, Attributor &A) : Base(IRP) {}
4540
4541	/// Returns true if HeapToStack conversion is assumed to be possible.
4542	virtual bool isAssumedHeapToStack(const CallBase &CB) const = 0;
4543
4544	/// Returns true if HeapToStack conversion is assumed and the CB is a
4545	/// callsite to a free operation to be removed.
4546	virtual bool isAssumedHeapToStackRemovedFree(CallBase &CB) const = 0;
4547
4548	/// Create an abstract attribute view for the position \p IRP.
4549	static AAHeapToStack &createForPosition(const IRPosition &IRP, Attributor &A);
4550
4551	/// See AbstractAttribute::getName()
4552	const std::string getName() const override { return "AAHeapToStack"; }
4553
4554	/// See AbstractAttribute::getIdAddr()
4555	const char *getIdAddr() const override { return &ID; }
4556
4557	/// This function should return true if the type of the \p AA is AAHeapToStack
4558	static bool classof(const AbstractAttribute *AA) {
4559	return (AA->getIdAddr() == &ID);
4560	}
4561
4562	/// Unique ID (due to the unique address)
4563	static const char ID;
4564	};
4565
4566	/// An abstract interface for privatizability.
4567	///
4568	/// A pointer is privatizable if it can be replaced by a new, private one.
4569	/// Privatizing pointer reduces the use count, interaction between unrelated
4570	/// code parts.
4571	///
4572	/// In order for a pointer to be privatizable its value cannot be observed
4573	/// (=nocapture), it is (for now) not written (=readonly & noalias), we know
4574	/// what values are necessary to make the private copy look like the original
4575	/// one, and the values we need can be loaded (=dereferenceable).
4576	struct AAPrivatizablePtr
4577	: public StateWrapper<BooleanState, AbstractAttribute> {
4578	using Base = StateWrapper<BooleanState, AbstractAttribute>;
4579	AAPrivatizablePtr(const IRPosition &IRP, Attributor &A) : Base(IRP) {}
4580
4581	/// See AbstractAttribute::isValidIRPositionForInit
4582	static bool isValidIRPositionForInit(Attributor &A, const IRPosition &IRP) {
4583	if (!IRP.getAssociatedType()->isPtrOrPtrVectorTy())
4584	return false;
4585	return AbstractAttribute::isValidIRPositionForInit(A, IRP);
4586	}
4587
4588	/// Returns true if pointer privatization is assumed to be possible.
4589	bool isAssumedPrivatizablePtr() const { return getAssumed(); }
4590
4591	/// Returns true if pointer privatization is known to be possible.
4592	bool isKnownPrivatizablePtr() const { return getKnown(); }
4593
4594	/// See AbstractAttribute::requiresCallersForArgOrFunction
4595	static bool requiresCallersForArgOrFunction() { return true; }
4596
4597	/// Return the type we can choose for a private copy of the underlying
4598	/// value. std::nullopt means it is not clear yet, nullptr means there is
4599	/// none.
4600	virtual std::optional<Type *> getPrivatizableType() const = 0;
4601
4602	/// Create an abstract attribute view for the position \p IRP.
4603	static AAPrivatizablePtr &createForPosition(const IRPosition &IRP,
4604	Attributor &A);
4605
4606	/// See AbstractAttribute::getName()
4607	const std::string getName() const override { return "AAPrivatizablePtr"; }
4608
4609	/// See AbstractAttribute::getIdAddr()
4610	const char *getIdAddr() const override { return &ID; }
4611
4612	/// This function should return true if the type of the \p AA is
4613	/// AAPricatizablePtr
4614	static bool classof(const AbstractAttribute *AA) {
4615	return (AA->getIdAddr() == &ID);
4616	}
4617
4618	/// Unique ID (due to the unique address)
4619	static const char ID;
4620	};
4621
4622	/// An abstract interface for memory access kind related attributes
4623	/// (readnone/readonly/writeonly).
4624	struct AAMemoryBehavior
4625	: public IRAttribute<
4626	Attribute::None,
4627	StateWrapper<BitIntegerState<uint8_t, 3>, AbstractAttribute>,
4628	AAMemoryBehavior> {
4629	AAMemoryBehavior(const IRPosition &IRP, Attributor &A) : IRAttribute(IRP) {}
4630
4631	/// See AbstractAttribute::hasTrivialInitializer.
4632	static bool hasTrivialInitializer() { return false; }
4633
4634	/// See AbstractAttribute::isValidIRPositionForInit
4635	static bool isValidIRPositionForInit(Attributor &A, const IRPosition &IRP) {
4636	if (!IRP.isFunctionScope() &&
4637	!IRP.getAssociatedType()->isPtrOrPtrVectorTy())
4638	return false;
4639	return IRAttribute::isValidIRPositionForInit(A, IRP);
4640	}
4641
4642	/// State encoding bits. A set bit in the state means the property holds.
4643	/// BEST_STATE is the best possible state, 0 the worst possible state.
4644	enum {
4645	NO_READS = 1 << 0,
4646	NO_WRITES = 1 << 1,
4647	NO_ACCESSES = NO_READS | NO_WRITES,
4648
4649	BEST_STATE = NO_ACCESSES,
4650	};
4651	static_assert(BEST_STATE == getBestState(), "Unexpected BEST_STATE value");
4652
4653	/// Return true if we know that the underlying value is not read or accessed
4654	/// in its respective scope.
4655	bool isKnownReadNone() const { return isKnown(BitsEncoding: NO_ACCESSES); }
4656
4657	/// Return true if we assume that the underlying value is not read or accessed
4658	/// in its respective scope.
4659	bool isAssumedReadNone() const { return isAssumed(BitsEncoding: NO_ACCESSES); }
4660
4661	/// Return true if we know that the underlying value is not accessed
4662	/// (=written) in its respective scope.
4663	bool isKnownReadOnly() const { return isKnown(BitsEncoding: NO_WRITES); }
4664
4665	/// Return true if we assume that the underlying value is not accessed
4666	/// (=written) in its respective scope.
4667	bool isAssumedReadOnly() const { return isAssumed(BitsEncoding: NO_WRITES); }
4668
4669	/// Return true if we know that the underlying value is not read in its
4670	/// respective scope.
4671	bool isKnownWriteOnly() const { return isKnown(BitsEncoding: NO_READS); }
4672
4673	/// Return true if we assume that the underlying value is not read in its
4674	/// respective scope.
4675	bool isAssumedWriteOnly() const { return isAssumed(BitsEncoding: NO_READS); }
4676
4677	/// Create an abstract attribute view for the position \p IRP.
4678	static AAMemoryBehavior &createForPosition(const IRPosition &IRP,
4679	Attributor &A);
4680
4681	/// See AbstractAttribute::getName()
4682	const std::string getName() const override { return "AAMemoryBehavior"; }
4683
4684	/// See AbstractAttribute::getIdAddr()
4685	const char *getIdAddr() const override { return &ID; }
4686
4687	/// This function should return true if the type of the \p AA is
4688	/// AAMemoryBehavior
4689	static bool classof(const AbstractAttribute *AA) {
4690	return (AA->getIdAddr() == &ID);
4691	}
4692
4693	/// Unique ID (due to the unique address)
4694	static const char ID;
4695	};
4696
4697	/// An abstract interface for all memory location attributes
4698	/// (readnone/argmemonly/inaccessiblememonly/inaccessibleorargmemonly).
4699	struct AAMemoryLocation
4700	: public IRAttribute<
4701	Attribute::None,
4702	StateWrapper<BitIntegerState<uint32_t, 511>, AbstractAttribute>,
4703	AAMemoryLocation> {
4704	using MemoryLocationsKind = StateType::base_t;
4705
4706	AAMemoryLocation(const IRPosition &IRP, Attributor &A) : IRAttribute(IRP) {}
4707
4708	/// See AbstractAttribute::requiresCalleeForCallBase.
4709	static bool requiresCalleeForCallBase() { return true; }
4710
4711	/// See AbstractAttribute::hasTrivialInitializer.
4712	static bool hasTrivialInitializer() { return false; }
4713
4714	/// See AbstractAttribute::isValidIRPositionForInit
4715	static bool isValidIRPositionForInit(Attributor &A, const IRPosition &IRP) {
4716	if (!IRP.isFunctionScope() &&
4717	!IRP.getAssociatedType()->isPtrOrPtrVectorTy())
4718	return false;
4719	return IRAttribute::isValidIRPositionForInit(A, IRP);
4720	}
4721
4722	/// Encoding of different locations that could be accessed by a memory
4723	/// access.
4724	enum {
4725	ALL_LOCATIONS = 0,
4726	NO_LOCAL_MEM = 1 << 0,
4727	NO_CONST_MEM = 1 << 1,
4728	NO_GLOBAL_INTERNAL_MEM = 1 << 2,
4729	NO_GLOBAL_EXTERNAL_MEM = 1 << 3,
4730	NO_GLOBAL_MEM = NO_GLOBAL_INTERNAL_MEM | NO_GLOBAL_EXTERNAL_MEM,
4731	NO_ARGUMENT_MEM = 1 << 4,
4732	NO_INACCESSIBLE_MEM = 1 << 5,
4733	NO_MALLOCED_MEM = 1 << 6,
4734	NO_UNKOWN_MEM = 1 << 7,
4735	NO_LOCATIONS = NO_LOCAL_MEM | NO_CONST_MEM | NO_GLOBAL_INTERNAL_MEM |
4736	NO_GLOBAL_EXTERNAL_MEM | NO_ARGUMENT_MEM |
4737	NO_INACCESSIBLE_MEM | NO_MALLOCED_MEM | NO_UNKOWN_MEM,
4738
4739	// Helper bit to track if we gave up or not.
4740	VALID_STATE = NO_LOCATIONS + 1,
4741
4742	BEST_STATE = NO_LOCATIONS | VALID_STATE,
4743	};
4744	static_assert(BEST_STATE == getBestState(), "Unexpected BEST_STATE value");
4745
4746	/// Return true if we know that the associated functions has no observable
4747	/// accesses.
4748	bool isKnownReadNone() const { return isKnown(BitsEncoding: NO_LOCATIONS); }
4749
4750	/// Return true if we assume that the associated functions has no observable
4751	/// accesses.
4752	bool isAssumedReadNone() const {
4753	return isAssumed(BitsEncoding: NO_LOCATIONS) || isAssumedStackOnly();
4754	}
4755
4756	/// Return true if we know that the associated functions has at most
4757	/// local/stack accesses.
4758	bool isKnowStackOnly() const {
4759	return isKnown(BitsEncoding: inverseLocation(Loc: NO_LOCAL_MEM, AndLocalMem: true, AndConstMem: true));
4760	}
4761
4762	/// Return true if we assume that the associated functions has at most
4763	/// local/stack accesses.
4764	bool isAssumedStackOnly() const {
4765	return isAssumed(BitsEncoding: inverseLocation(Loc: NO_LOCAL_MEM, AndLocalMem: true, AndConstMem: true));
4766	}
4767
4768	/// Return true if we know that the underlying value will only access
4769	/// inaccesible memory only (see Attribute::InaccessibleMemOnly).
4770	bool isKnownInaccessibleMemOnly() const {
4771	return isKnown(BitsEncoding: inverseLocation(Loc: NO_INACCESSIBLE_MEM, AndLocalMem: true, AndConstMem: true));
4772	}
4773
4774	/// Return true if we assume that the underlying value will only access
4775	/// inaccesible memory only (see Attribute::InaccessibleMemOnly).
4776	bool isAssumedInaccessibleMemOnly() const {
4777	return isAssumed(BitsEncoding: inverseLocation(Loc: NO_INACCESSIBLE_MEM, AndLocalMem: true, AndConstMem: true));
4778	}
4779
4780	/// Return true if we know that the underlying value will only access
4781	/// argument pointees (see Attribute::ArgMemOnly).
4782	bool isKnownArgMemOnly() const {
4783	return isKnown(BitsEncoding: inverseLocation(Loc: NO_ARGUMENT_MEM, AndLocalMem: true, AndConstMem: true));
4784	}
4785
4786	/// Return true if we assume that the underlying value will only access
4787	/// argument pointees (see Attribute::ArgMemOnly).
4788	bool isAssumedArgMemOnly() const {
4789	return isAssumed(BitsEncoding: inverseLocation(Loc: NO_ARGUMENT_MEM, AndLocalMem: true, AndConstMem: true));
4790	}
4791
4792	/// Return true if we know that the underlying value will only access
4793	/// inaccesible memory or argument pointees (see
4794	/// Attribute::InaccessibleOrArgMemOnly).
4795	bool isKnownInaccessibleOrArgMemOnly() const {
4796	return isKnown(
4797	BitsEncoding: inverseLocation(Loc: NO_INACCESSIBLE_MEM | NO_ARGUMENT_MEM, AndLocalMem: true, AndConstMem: true));
4798	}
4799
4800	/// Return true if we assume that the underlying value will only access
4801	/// inaccesible memory or argument pointees (see
4802	/// Attribute::InaccessibleOrArgMemOnly).
4803	bool isAssumedInaccessibleOrArgMemOnly() const {
4804	return isAssumed(
4805	BitsEncoding: inverseLocation(Loc: NO_INACCESSIBLE_MEM | NO_ARGUMENT_MEM, AndLocalMem: true, AndConstMem: true));
4806	}
4807
4808	/// Return true if the underlying value may access memory through arguement
4809	/// pointers of the associated function, if any.
4810	bool mayAccessArgMem() const { return !isAssumed(BitsEncoding: NO_ARGUMENT_MEM); }
4811
4812	/// Return true if only the memory locations specififed by \p MLK are assumed
4813	/// to be accessed by the associated function.
4814	bool isAssumedSpecifiedMemOnly(MemoryLocationsKind MLK) const {
4815	return isAssumed(BitsEncoding: MLK);
4816	}
4817
4818	/// Return the locations that are assumed to be not accessed by the associated
4819	/// function, if any.
4820	MemoryLocationsKind getAssumedNotAccessedLocation() const {
4821	return getAssumed();
4822	}
4823
4824	/// Return the inverse of location \p Loc, thus for NO_XXX the return
4825	/// describes ONLY_XXX. The flags \p AndLocalMem and \p AndConstMem determine
4826	/// if local (=stack) and constant memory are allowed as well. Most of the
4827	/// time we do want them to be included, e.g., argmemonly allows accesses via
4828	/// argument pointers or local or constant memory accesses.
4829	static MemoryLocationsKind
4830	inverseLocation(MemoryLocationsKind Loc, bool AndLocalMem, bool AndConstMem) {
4831	return NO_LOCATIONS & ~(Loc | (AndLocalMem ? NO_LOCAL_MEM : 0) |
4832	(AndConstMem ? NO_CONST_MEM : 0));
4833	};
4834
4835	/// Return the locations encoded by \p MLK as a readable string.
4836	static std::string getMemoryLocationsAsStr(MemoryLocationsKind MLK);
4837
4838	/// Simple enum to distinguish read/write/read-write accesses.
4839	enum AccessKind {
4840	NONE = 0,
4841	READ = 1 << 0,
4842	WRITE = 1 << 1,
4843	READ_WRITE = READ | WRITE,
4844	};
4845
4846	/// Check \p Pred on all accesses to the memory kinds specified by \p MLK.
4847	///
4848	/// This method will evaluate \p Pred on all accesses (access instruction +
4849	/// underlying accessed memory pointer) and it will return true if \p Pred
4850	/// holds every time.
4851	virtual bool checkForAllAccessesToMemoryKind(
4852	function_ref<bool(const Instruction *, const Value *, AccessKind,
4853	MemoryLocationsKind)>
4854	Pred,
4855	MemoryLocationsKind MLK) const = 0;
4856
4857	/// Create an abstract attribute view for the position \p IRP.
4858	static AAMemoryLocation &createForPosition(const IRPosition &IRP,
4859	Attributor &A);
4860
4861	/// See AbstractState::getAsStr(Attributor).
4862	const std::string getAsStr(Attributor *A) const override {
4863	return getMemoryLocationsAsStr(MLK: getAssumedNotAccessedLocation());
4864	}
4865
4866	/// See AbstractAttribute::getName()
4867	const std::string getName() const override { return "AAMemoryLocation"; }
4868
4869	/// See AbstractAttribute::getIdAddr()
4870	const char *getIdAddr() const override { return &ID; }
4871
4872	/// This function should return true if the type of the \p AA is
4873	/// AAMemoryLocation
4874	static bool classof(const AbstractAttribute *AA) {
4875	return (AA->getIdAddr() == &ID);
4876	}
4877
4878	/// Unique ID (due to the unique address)
4879	static const char ID;
4880	};
4881
4882	/// An abstract interface for range value analysis.
4883	struct AAValueConstantRange
4884	: public StateWrapper<IntegerRangeState, AbstractAttribute, uint32_t> {
4885	using Base = StateWrapper<IntegerRangeState, AbstractAttribute, uint32_t>;
4886	AAValueConstantRange(const IRPosition &IRP, Attributor &A)
4887	: Base(IRP, IRP.getAssociatedType()->getIntegerBitWidth()) {}
4888
4889	/// See AbstractAttribute::isValidIRPositionForInit
4890	static bool isValidIRPositionForInit(Attributor &A, const IRPosition &IRP) {
4891	if (!IRP.getAssociatedType()->isIntegerTy())
4892	return false;
4893	return AbstractAttribute::isValidIRPositionForInit(A, IRP);
4894	}
4895
4896	/// See AbstractAttribute::requiresCallersForArgOrFunction
4897	static bool requiresCallersForArgOrFunction() { return true; }
4898
4899	/// See AbstractAttribute::getState(...).
4900	IntegerRangeState &getState() override { return *this; }
4901	const IntegerRangeState &getState() const override { return *this; }
4902
4903	/// Create an abstract attribute view for the position \p IRP.
4904	static AAValueConstantRange &createForPosition(const IRPosition &IRP,
4905	Attributor &A);
4906
4907	/// Return an assumed range for the associated value a program point \p CtxI.
4908	/// If \p I is nullptr, simply return an assumed range.
4909	virtual ConstantRange
4910	getAssumedConstantRange(Attributor &A,
4911	const Instruction *CtxI = nullptr) const = 0;
4912
4913	/// Return a known range for the associated value at a program point \p CtxI.
4914	/// If \p I is nullptr, simply return a known range.
4915	virtual ConstantRange
4916	getKnownConstantRange(Attributor &A,
4917	const Instruction *CtxI = nullptr) const = 0;
4918
4919	/// Return an assumed constant for the associated value a program point \p
4920	/// CtxI.
4921	std::optional<Constant *>
4922	getAssumedConstant(Attributor &A, const Instruction *CtxI = nullptr) const {
4923	ConstantRange RangeV = getAssumedConstantRange(A, CtxI);
4924	if (auto *C = RangeV.getSingleElement()) {
4925	Type *Ty = getAssociatedValue().getType();
4926	return cast_or_null<Constant>(
4927	Val: AA::getWithType(V&: *ConstantInt::get(Context&: Ty->getContext(), V: *C), Ty&: *Ty));
4928	}
4929	if (RangeV.isEmptySet())
4930	return std::nullopt;
4931	return nullptr;
4932	}
4933
4934	/// See AbstractAttribute::getName()
4935	const std::string getName() const override { return "AAValueConstantRange"; }
4936
4937	/// See AbstractAttribute::getIdAddr()
4938	const char *getIdAddr() const override { return &ID; }
4939
4940	/// This function should return true if the type of the \p AA is
4941	/// AAValueConstantRange
4942	static bool classof(const AbstractAttribute *AA) {
4943	return (AA->getIdAddr() == &ID);
4944	}
4945
4946	/// Unique ID (due to the unique address)
4947	static const char ID;
4948	};
4949
4950	/// A class for a set state.
4951	/// The assumed boolean state indicates whether the corresponding set is full
4952	/// set or not. If the assumed state is false, this is the worst state. The
4953	/// worst state (invalid state) of set of potential values is when the set
4954	/// contains every possible value (i.e. we cannot in any way limit the value
4955	/// that the target position can take). That never happens naturally, we only
4956	/// force it. As for the conditions under which we force it, see
4957	/// AAPotentialConstantValues.
4958	template <typename MemberTy> struct PotentialValuesState : AbstractState {
4959	using SetTy = SmallSetVector<MemberTy, 8>;
4960
4961	PotentialValuesState() : IsValidState(true), UndefIsContained(false) {}
4962
4963	PotentialValuesState(bool IsValid)
4964	: IsValidState(IsValid), UndefIsContained(false) {}
4965
4966	/// See AbstractState::isValidState(...)
4967	bool isValidState() const override { return IsValidState.isValidState(); }
4968
4969	/// See AbstractState::isAtFixpoint(...)
4970	bool isAtFixpoint() const override { return IsValidState.isAtFixpoint(); }
4971
4972	/// See AbstractState::indicatePessimisticFixpoint(...)
4973	ChangeStatus indicatePessimisticFixpoint() override {
4974	return IsValidState.indicatePessimisticFixpoint();
4975	}
4976
4977	/// See AbstractState::indicateOptimisticFixpoint(...)
4978	ChangeStatus indicateOptimisticFixpoint() override {
4979	return IsValidState.indicateOptimisticFixpoint();
4980	}
4981
4982	/// Return the assumed state
4983	PotentialValuesState &getAssumed() { return *this; }
4984	const PotentialValuesState &getAssumed() const { return *this; }
4985
4986	/// Return this set. We should check whether this set is valid or not by
4987	/// isValidState() before calling this function.
4988	const SetTy &getAssumedSet() const {
4989	assert(isValidState() && "This set shoud not be used when it is invalid!");
4990	return Set;
4991	}
4992
4993	/// Returns whether this state contains an undef value or not.
4994	bool undefIsContained() const {
4995	assert(isValidState() && "This flag shoud not be used when it is invalid!");
4996	return UndefIsContained;
4997	}
4998
4999	bool operator==(const PotentialValuesState &RHS) const {
5000	if (isValidState() != RHS.isValidState())
5001	return false;
5002	if (!isValidState() && !RHS.isValidState())
5003	return true;
5004	if (undefIsContained() != RHS.undefIsContained())
5005	return false;
5006	return Set == RHS.getAssumedSet();
5007	}
5008
5009	/// Maximum number of potential values to be tracked.
5010	/// This is set by -attributor-max-potential-values command line option
5011	static unsigned MaxPotentialValues;
5012
5013	/// Return empty set as the best state of potential values.
5014	static PotentialValuesState getBestState() {
5015	return PotentialValuesState(true);
5016	}
5017
5018	static PotentialValuesState getBestState(const PotentialValuesState &PVS) {
5019	return getBestState();
5020	}
5021
5022	/// Return full set as the worst state of potential values.
5023	static PotentialValuesState getWorstState() {
5024	return PotentialValuesState(false);
5025	}
5026
5027	/// Union assumed set with the passed value.
5028	void unionAssumed(const MemberTy &C) { insert(C); }
5029
5030	/// Union assumed set with assumed set of the passed state \p PVS.
5031	void unionAssumed(const PotentialValuesState &PVS) { unionWith(R: PVS); }
5032
5033	/// Union assumed set with an undef value.
5034	void unionAssumedWithUndef() { unionWithUndef(); }
5035
5036	/// "Clamp" this state with \p PVS.
5037	PotentialValuesState operator^=(const PotentialValuesState &PVS) {
5038	IsValidState ^= PVS.IsValidState;
5039	unionAssumed(PVS);
5040	return *this;
5041	}
5042
5043	PotentialValuesState operator&=(const PotentialValuesState &PVS) {
5044	IsValidState &= PVS.IsValidState;
5045	unionAssumed(PVS);
5046	return *this;
5047	}
5048
5049	bool contains(const MemberTy &V) const {
5050	return !isValidState() ? true : Set.contains(V);
5051	}
5052
5053	protected:
5054	SetTy &getAssumedSet() {
5055	assert(isValidState() && "This set shoud not be used when it is invalid!");
5056	return Set;
5057	}
5058
5059	private:
5060	/// Check the size of this set, and invalidate when the size is no
5061	/// less than \p MaxPotentialValues threshold.
5062	void checkAndInvalidate() {
5063	if (Set.size() >= MaxPotentialValues)
5064	indicatePessimisticFixpoint();
5065	else
5066	reduceUndefValue();
5067	}
5068
5069	/// If this state contains both undef and not undef, we can reduce
5070	/// undef to the not undef value.
5071	void reduceUndefValue() { UndefIsContained = UndefIsContained & Set.empty(); }
5072
5073	/// Insert an element into this set.
5074	void insert(const MemberTy &C) {
5075	if (!isValidState())
5076	return;
5077	Set.insert(C);
5078	checkAndInvalidate();
5079	}
5080
5081	/// Take union with R.
5082	void unionWith(const PotentialValuesState &R) {
5083	/// If this is a full set, do nothing.
5084	if (!isValidState())
5085	return;
5086	/// If R is full set, change L to a full set.
5087	if (!R.isValidState()) {
5088	indicatePessimisticFixpoint();
5089	return;
5090	}
5091	for (const MemberTy &C : R.Set)
5092	Set.insert(C);
5093	UndefIsContained |= R.undefIsContained();
5094	checkAndInvalidate();
5095	}
5096
5097	/// Take union with an undef value.
5098	void unionWithUndef() {
5099	UndefIsContained = true;
5100	reduceUndefValue();
5101	}
5102
5103	/// Take intersection with R.
5104	void intersectWith(const PotentialValuesState &R) {
5105	/// If R is a full set, do nothing.
5106	if (!R.isValidState())
5107	return;
5108	/// If this is a full set, change this to R.
5109	if (!isValidState()) {
5110	*this = R;
5111	return;
5112	}
5113	SetTy IntersectSet;
5114	for (const MemberTy &C : Set) {
5115	if (R.Set.count(C))
5116	IntersectSet.insert(C);
5117	}
5118	Set = IntersectSet;
5119	UndefIsContained &= R.undefIsContained();
5120	reduceUndefValue();
5121	}
5122
5123	/// A helper state which indicate whether this state is valid or not.
5124	BooleanState IsValidState;
5125
5126	/// Container for potential values
5127	SetTy Set;
5128
5129	/// Flag for undef value
5130	bool UndefIsContained;
5131	};
5132
5133	struct DenormalFPMathState : public AbstractState {
5134	struct DenormalState {
5135	DenormalMode Mode = DenormalMode::getInvalid();
5136	DenormalMode ModeF32 = DenormalMode::getInvalid();
5137
5138	bool operator==(const DenormalState Other) const {
5139	return Mode == Other.Mode && ModeF32 == Other.ModeF32;
5140	}
5141
5142	bool operator!=(const DenormalState Other) const {
5143	return Mode != Other.Mode || ModeF32 != Other.ModeF32;
5144	}
5145
5146	bool isValid() const {
5147	return Mode.isValid() && ModeF32.isValid();
5148	}
5149
5150	static DenormalMode::DenormalModeKind
5151	unionDenormalKind(DenormalMode::DenormalModeKind Callee,
5152	DenormalMode::DenormalModeKind Caller) {
5153	if (Caller == Callee)
5154	return Caller;
5155	if (Callee == DenormalMode::Dynamic)
5156	return Caller;
5157	if (Caller == DenormalMode::Dynamic)
5158	return Callee;
5159	return DenormalMode::Invalid;
5160	}
5161
5162	static DenormalMode unionAssumed(DenormalMode Callee, DenormalMode Caller) {
5163	return DenormalMode{unionDenormalKind(Callee: Callee.Output, Caller: Caller.Output),
5164	unionDenormalKind(Callee: Callee.Input, Caller: Caller.Input)};
5165	}
5166
5167	DenormalState unionWith(DenormalState Caller) const {
5168	DenormalState Callee(*this);
5169	Callee.Mode = unionAssumed(Callee: Callee.Mode, Caller: Caller.Mode);
5170	Callee.ModeF32 = unionAssumed(Callee: Callee.ModeF32, Caller: Caller.ModeF32);
5171	return Callee;
5172	}
5173	};
5174
5175	DenormalState Known;
5176
5177	/// Explicitly track whether we've hit a fixed point.
5178	bool IsAtFixedpoint = false;
5179
5180	DenormalFPMathState() = default;
5181
5182	DenormalState getKnown() const { return Known; }
5183
5184	// There's only really known or unknown, there's no speculatively assumable
5185	// state.
5186	DenormalState getAssumed() const { return Known; }
5187
5188	bool isValidState() const override {
5189	return Known.isValid();
5190	}
5191
5192	/// Return true if there are no dynamic components to the denormal mode worth
5193	/// specializing.
5194	bool isModeFixed() const {
5195	return Known.Mode.Input != DenormalMode::Dynamic &&
5196	Known.Mode.Output != DenormalMode::Dynamic &&
5197	Known.ModeF32.Input != DenormalMode::Dynamic &&
5198	Known.ModeF32.Output != DenormalMode::Dynamic;
5199	}
5200
5201	bool isAtFixpoint() const override {
5202	return IsAtFixedpoint;
5203	}
5204
5205	ChangeStatus indicateFixpoint() {
5206	bool Changed = !IsAtFixedpoint;
5207	IsAtFixedpoint = true;
5208	return Changed ? ChangeStatus::CHANGED : ChangeStatus::UNCHANGED;
5209	}
5210
5211	ChangeStatus indicateOptimisticFixpoint() override {
5212	return indicateFixpoint();
5213	}
5214
5215	ChangeStatus indicatePessimisticFixpoint() override {
5216	return indicateFixpoint();
5217	}
5218
5219	DenormalFPMathState operator^=(const DenormalFPMathState &Caller) {
5220	Known = Known.unionWith(Caller: Caller.getKnown());
5221	return *this;
5222	}
5223	};
5224
5225	using PotentialConstantIntValuesState = PotentialValuesState<APInt>;
5226	using PotentialLLVMValuesState =
5227	PotentialValuesState<std::pair<AA::ValueAndContext, AA::ValueScope>>;
5228
5229	raw_ostream &operator<<(raw_ostream &OS,
5230	const PotentialConstantIntValuesState &R);
5231	raw_ostream &operator<<(raw_ostream &OS, const PotentialLLVMValuesState &R);
5232
5233	/// An abstract interface for potential values analysis.
5234	///
5235	/// This AA collects potential values for each IR position.
5236	/// An assumed set of potential values is initialized with the empty set (the
5237	/// best state) and it will grow monotonically as we find more potential values
5238	/// for this position.
5239	/// The set might be forced to the worst state, that is, to contain every
5240	/// possible value for this position in 2 cases.
5241	/// 1. We surpassed the \p MaxPotentialValues threshold. This includes the
5242	/// case that this position is affected (e.g. because of an operation) by a
5243	/// Value that is in the worst state.
5244	/// 2. We tried to initialize on a Value that we cannot handle (e.g. an
5245	/// operator we do not currently handle).
5246	///
5247	/// For non constant integers see AAPotentialValues.
5248	struct AAPotentialConstantValues
5249	: public StateWrapper<PotentialConstantIntValuesState, AbstractAttribute> {
5250	using Base = StateWrapper<PotentialConstantIntValuesState, AbstractAttribute>;
5251	AAPotentialConstantValues(const IRPosition &IRP, Attributor &A) : Base(IRP) {}
5252
5253	/// See AbstractAttribute::isValidIRPositionForInit
5254	static bool isValidIRPositionForInit(Attributor &A, const IRPosition &IRP) {
5255	if (!IRP.getAssociatedType()->isIntegerTy())
5256	return false;
5257	return AbstractAttribute::isValidIRPositionForInit(A, IRP);
5258	}
5259
5260	/// See AbstractAttribute::requiresCallersForArgOrFunction
5261	static bool requiresCallersForArgOrFunction() { return true; }
5262
5263	/// See AbstractAttribute::getState(...).
5264	PotentialConstantIntValuesState &getState() override { return *this; }
5265	const PotentialConstantIntValuesState &getState() const override {
5266	return *this;
5267	}
5268
5269	/// Create an abstract attribute view for the position \p IRP.
5270	static AAPotentialConstantValues &createForPosition(const IRPosition &IRP,
5271	Attributor &A);
5272
5273	/// Return assumed constant for the associated value
5274	std::optional<Constant *>
5275	getAssumedConstant(Attributor &A, const Instruction *CtxI = nullptr) const {
5276	if (!isValidState())
5277	return nullptr;
5278	if (getAssumedSet().size() == 1) {
5279	Type *Ty = getAssociatedValue().getType();
5280	return cast_or_null<Constant>(Val: AA::getWithType(
5281	V&: *ConstantInt::get(Context&: Ty->getContext(), V: *(getAssumedSet().begin())),
5282	Ty&: *Ty));
5283	}
5284	if (getAssumedSet().size() == 0) {
5285	if (undefIsContained())
5286	return UndefValue::get(T: getAssociatedValue().getType());
5287	return std::nullopt;
5288	}
5289
5290	return nullptr;
5291	}
5292
5293	/// See AbstractAttribute::getName()
5294	const std::string getName() const override {
5295	return "AAPotentialConstantValues";
5296	}
5297
5298	/// See AbstractAttribute::getIdAddr()
5299	const char *getIdAddr() const override { return &ID; }
5300
5301	/// This function should return true if the type of the \p AA is
5302	/// AAPotentialConstantValues
5303	static bool classof(const AbstractAttribute *AA) {
5304	return (AA->getIdAddr() == &ID);
5305	}
5306
5307	/// Unique ID (due to the unique address)
5308	static const char ID;
5309	};
5310
5311	struct AAPotentialValues
5312	: public StateWrapper<PotentialLLVMValuesState, AbstractAttribute> {
5313	using Base = StateWrapper<PotentialLLVMValuesState, AbstractAttribute>;
5314	AAPotentialValues(const IRPosition &IRP, Attributor &A) : Base(IRP) {}
5315
5316	/// See AbstractAttribute::requiresCallersForArgOrFunction
5317	static bool requiresCallersForArgOrFunction() { return true; }
5318
5319	/// See AbstractAttribute::getState(...).
5320	PotentialLLVMValuesState &getState() override { return *this; }
5321	const PotentialLLVMValuesState &getState() const override { return *this; }
5322
5323	/// Create an abstract attribute view for the position \p IRP.
5324	static AAPotentialValues &createForPosition(const IRPosition &IRP,
5325	Attributor &A);
5326
5327	/// Extract the single value in \p Values if any.
5328	static Value *getSingleValue(Attributor &A, const AbstractAttribute &AA,
5329	const IRPosition &IRP,
5330	SmallVectorImpl<AA::ValueAndContext> &Values);
5331
5332	/// See AbstractAttribute::getName()
5333	const std::string getName() const override { return "AAPotentialValues"; }
5334
5335	/// See AbstractAttribute::getIdAddr()
5336	const char *getIdAddr() const override { return &ID; }
5337
5338	/// This function should return true if the type of the \p AA is
5339	/// AAPotentialValues
5340	static bool classof(const AbstractAttribute *AA) {
5341	return (AA->getIdAddr() == &ID);
5342	}
5343
5344	/// Unique ID (due to the unique address)
5345	static const char ID;
5346
5347	private:
5348	virtual bool getAssumedSimplifiedValues(
5349	Attributor &A, SmallVectorImpl<AA::ValueAndContext> &Values,
5350	AA::ValueScope, bool RecurseForSelectAndPHI = false) const = 0;
5351
5352	friend struct Attributor;
5353	};
5354
5355	/// An abstract interface for all noundef attributes.
5356	struct AANoUndef
5357	: public IRAttribute<Attribute::NoUndef,
5358	StateWrapper<BooleanState, AbstractAttribute>,
5359	AANoUndef> {
5360	AANoUndef(const IRPosition &IRP, Attributor &A) : IRAttribute(IRP) {}
5361
5362	/// See IRAttribute::isImpliedByUndef
5363	static bool isImpliedByUndef() { return false; }
5364
5365	/// See IRAttribute::isImpliedByPoison
5366	static bool isImpliedByPoison() { return false; }
5367
5368	/// See IRAttribute::isImpliedByIR
5369	static bool isImpliedByIR(Attributor &A, const IRPosition &IRP,
5370	Attribute::AttrKind ImpliedAttributeKind,
5371	bool IgnoreSubsumingPositions = false);
5372
5373	/// Return true if we assume that the underlying value is noundef.
5374	bool isAssumedNoUndef() const { return getAssumed(); }
5375
5376	/// Return true if we know that underlying value is noundef.
5377	bool isKnownNoUndef() const { return getKnown(); }
5378
5379	/// Create an abstract attribute view for the position \p IRP.
5380	static AANoUndef &createForPosition(const IRPosition &IRP, Attributor &A);
5381
5382	/// See AbstractAttribute::getName()
5383	const std::string getName() const override { return "AANoUndef"; }
5384
5385	/// See AbstractAttribute::getIdAddr()
5386	const char *getIdAddr() const override { return &ID; }
5387
5388	/// This function should return true if the type of the \p AA is AANoUndef
5389	static bool classof(const AbstractAttribute *AA) {
5390	return (AA->getIdAddr() == &ID);
5391	}
5392
5393	/// Unique ID (due to the unique address)
5394	static const char ID;
5395	};
5396
5397	struct AANoFPClass
5398	: public IRAttribute<
5399	Attribute::NoFPClass,
5400	StateWrapper<BitIntegerState<uint32_t, fcAllFlags, fcNone>,
5401	AbstractAttribute>,
5402	AANoFPClass> {
5403	using Base = StateWrapper<BitIntegerState<uint32_t, fcAllFlags, fcNone>,
5404	AbstractAttribute>;
5405
5406	AANoFPClass(const IRPosition &IRP, Attributor &A) : IRAttribute(IRP) {}
5407
5408	/// See AbstractAttribute::isValidIRPositionForInit
5409	static bool isValidIRPositionForInit(Attributor &A, const IRPosition &IRP) {
5410	Type *Ty = IRP.getAssociatedType();
5411	do {
5412	if (Ty->isFPOrFPVectorTy())
5413	return IRAttribute::isValidIRPositionForInit(A, IRP);
5414	if (!Ty->isArrayTy())
5415	break;
5416	Ty = Ty->getArrayElementType();
5417	} while (true);
5418	return false;
5419	}
5420
5421	/// Return true if we assume that the underlying value is nofpclass.
5422	FPClassTest getAssumedNoFPClass() const {
5423	return static_cast<FPClassTest>(getAssumed());
5424	}
5425
5426	/// Create an abstract attribute view for the position \p IRP.
5427	static AANoFPClass &createForPosition(const IRPosition &IRP, Attributor &A);
5428
5429	/// See AbstractAttribute::getName()
5430	const std::string getName() const override { return "AANoFPClass"; }
5431
5432	/// See AbstractAttribute::getIdAddr()
5433	const char *getIdAddr() const override { return &ID; }
5434
5435	/// This function should return true if the type of the \p AA is AANoFPClass
5436	static bool classof(const AbstractAttribute *AA) {
5437	return (AA->getIdAddr() == &ID);
5438	}
5439
5440	/// Unique ID (due to the unique address)
5441	static const char ID;
5442	};
5443
5444	struct AACallGraphNode;
5445	struct AACallEdges;
5446
5447	/// An Iterator for call edges, creates AACallEdges attributes in a lazy way.
5448	/// This iterator becomes invalid if the underlying edge list changes.
5449	/// So This shouldn't outlive a iteration of Attributor.
5450	class AACallEdgeIterator
5451	: public iterator_adaptor_base<AACallEdgeIterator,
5452	SetVector<Function *>::iterator> {
5453	AACallEdgeIterator(Attributor &A, SetVector<Function *>::iterator Begin)
5454	: iterator_adaptor_base(Begin), A(A) {}
5455
5456	public:
5457	AACallGraphNode *operator*() const;
5458
5459	private:
5460	Attributor &A;
5461	friend AACallEdges;
5462	friend AttributorCallGraph;
5463	};
5464
5465	struct AACallGraphNode {
5466	AACallGraphNode(Attributor &A) : A(A) {}
5467	virtual ~AACallGraphNode() = default;
5468
5469	virtual AACallEdgeIterator optimisticEdgesBegin() const = 0;
5470	virtual AACallEdgeIterator optimisticEdgesEnd() const = 0;
5471
5472	/// Iterator range for exploring the call graph.
5473	iterator_range<AACallEdgeIterator> optimisticEdgesRange() const {
5474	return iterator_range<AACallEdgeIterator>(optimisticEdgesBegin(),
5475	optimisticEdgesEnd());
5476	}
5477
5478	protected:
5479	/// Reference to Attributor needed for GraphTraits implementation.
5480	Attributor &A;
5481	};
5482
5483	/// An abstract state for querying live call edges.
5484	/// This interface uses the Attributor's optimistic liveness
5485	/// information to compute the edges that are alive.
5486	struct AACallEdges : public StateWrapper<BooleanState, AbstractAttribute>,
5487	AACallGraphNode {
5488	using Base = StateWrapper<BooleanState, AbstractAttribute>;
5489
5490	AACallEdges(const IRPosition &IRP, Attributor &A)
5491	: Base(IRP), AACallGraphNode(A) {}
5492
5493	/// See AbstractAttribute::requiresNonAsmForCallBase.
5494	static bool requiresNonAsmForCallBase() { return false; }
5495
5496	/// Get the optimistic edges.
5497	virtual const SetVector<Function *> &getOptimisticEdges() const = 0;
5498
5499	/// Is there any call with a unknown callee.
5500	virtual bool hasUnknownCallee() const = 0;
5501
5502	/// Is there any call with a unknown callee, excluding any inline asm.
5503	virtual bool hasNonAsmUnknownCallee() const = 0;
5504
5505	/// Iterator for exploring the call graph.
5506	AACallEdgeIterator optimisticEdgesBegin() const override {
5507	return AACallEdgeIterator(A, getOptimisticEdges().begin());
5508	}
5509
5510	/// Iterator for exploring the call graph.
5511	AACallEdgeIterator optimisticEdgesEnd() const override {
5512	return AACallEdgeIterator(A, getOptimisticEdges().end());
5513	}
5514
5515	/// Create an abstract attribute view for the position \p IRP.
5516	static AACallEdges &createForPosition(const IRPosition &IRP, Attributor &A);
5517
5518	/// See AbstractAttribute::getName()
5519	const std::string getName() const override { return "AACallEdges"; }
5520
5521	/// See AbstractAttribute::getIdAddr()
5522	const char *getIdAddr() const override { return &ID; }
5523
5524	/// This function should return true if the type of the \p AA is AACallEdges.
5525	static bool classof(const AbstractAttribute *AA) {
5526	return (AA->getIdAddr() == &ID);
5527	}
5528
5529	/// Unique ID (due to the unique address)
5530	static const char ID;
5531	};
5532
5533	// Synthetic root node for the Attributor's internal call graph.
5534	struct AttributorCallGraph : public AACallGraphNode {
5535	AttributorCallGraph(Attributor &A) : AACallGraphNode(A) {}
5536	virtual ~AttributorCallGraph() = default;
5537
5538	AACallEdgeIterator optimisticEdgesBegin() const override {
5539	return AACallEdgeIterator(A, A.Functions.begin());
5540	}
5541
5542	AACallEdgeIterator optimisticEdgesEnd() const override {
5543	return AACallEdgeIterator(A, A.Functions.end());
5544	}
5545
5546	/// Force populate the entire call graph.
5547	void populateAll() const {
5548	for (const AACallGraphNode *AA : optimisticEdgesRange()) {
5549	// Nothing else to do here.
5550	(void)AA;
5551	}
5552	}
5553
5554	void print();
5555	};
5556
5557	template <> struct GraphTraits<AACallGraphNode *> {
5558	using NodeRef = AACallGraphNode *;
5559	using ChildIteratorType = AACallEdgeIterator;
5560
5561	static AACallEdgeIterator child_begin(AACallGraphNode *Node) {
5562	return Node->optimisticEdgesBegin();
5563	}
5564
5565	static AACallEdgeIterator child_end(AACallGraphNode *Node) {
5566	return Node->optimisticEdgesEnd();
5567	}
5568	};
5569
5570	template <>
5571	struct GraphTraits<AttributorCallGraph *>
5572	: public GraphTraits<AACallGraphNode *> {
5573	using nodes_iterator = AACallEdgeIterator;
5574
5575	static AACallGraphNode *getEntryNode(AttributorCallGraph *G) {
5576	return static_cast<AACallGraphNode *>(G);
5577	}
5578
5579	static AACallEdgeIterator nodes_begin(const AttributorCallGraph *G) {
5580	return G->optimisticEdgesBegin();
5581	}
5582
5583	static AACallEdgeIterator nodes_end(const AttributorCallGraph *G) {
5584	return G->optimisticEdgesEnd();
5585	}
5586	};
5587
5588	template <>
5589	struct DOTGraphTraits<AttributorCallGraph *> : public DefaultDOTGraphTraits {
5590	DOTGraphTraits(bool Simple = false) : DefaultDOTGraphTraits(Simple) {}
5591
5592	std::string getNodeLabel(const AACallGraphNode *Node,
5593	const AttributorCallGraph *Graph) {
5594	const AACallEdges *AACE = static_cast<const AACallEdges *>(Node);
5595	return AACE->getAssociatedFunction()->getName().str();
5596	}
5597
5598	static bool isNodeHidden(const AACallGraphNode *Node,
5599	const AttributorCallGraph *Graph) {
5600	// Hide the synth root.
5601	return static_cast<const AACallGraphNode *>(Graph) == Node;
5602	}
5603	};
5604
5605	struct AAExecutionDomain
5606	: public StateWrapper<BooleanState, AbstractAttribute> {
5607	using Base = StateWrapper<BooleanState, AbstractAttribute>;
5608	AAExecutionDomain(const IRPosition &IRP, Attributor &A) : Base(IRP) {}
5609
5610	/// Summary about the execution domain of a block or instruction.
5611	struct ExecutionDomainTy {
5612	using BarriersSetTy = SmallPtrSet<CallBase *, 2>;
5613	using AssumesSetTy = SmallPtrSet<AssumeInst *, 4>;
5614
5615	void addAssumeInst(Attributor &A, AssumeInst &AI) {
5616	EncounteredAssumes.insert(Ptr: &AI);
5617	}
5618
5619	void addAlignedBarrier(Attributor &A, CallBase &CB) {
5620	AlignedBarriers.insert(Ptr: &CB);
5621	}
5622
5623	void clearAssumeInstAndAlignedBarriers() {
5624	EncounteredAssumes.clear();
5625	AlignedBarriers.clear();
5626	}
5627
5628	bool IsExecutedByInitialThreadOnly = true;
5629	bool IsReachedFromAlignedBarrierOnly = true;
5630	bool IsReachingAlignedBarrierOnly = true;
5631	bool EncounteredNonLocalSideEffect = false;
5632	BarriersSetTy AlignedBarriers;
5633	AssumesSetTy EncounteredAssumes;
5634	};
5635
5636	/// Create an abstract attribute view for the position \p IRP.
5637	static AAExecutionDomain &createForPosition(const IRPosition &IRP,
5638	Attributor &A);
5639
5640	/// See AbstractAttribute::getName().
5641	const std::string getName() const override { return "AAExecutionDomain"; }
5642
5643	/// See AbstractAttribute::getIdAddr().
5644	const char *getIdAddr() const override { return &ID; }
5645
5646	/// Check if an instruction is executed only by the initial thread.
5647	bool isExecutedByInitialThreadOnly(const Instruction &I) const {
5648	return isExecutedByInitialThreadOnly(*I.getParent());
5649	}
5650
5651	/// Check if a basic block is executed only by the initial thread.
5652	virtual bool isExecutedByInitialThreadOnly(const BasicBlock &) const = 0;
5653
5654	/// Check if the instruction \p I is executed in an aligned region, that is,
5655	/// the synchronizing effects before and after \p I are both aligned barriers.
5656	/// This effectively means all threads execute \p I together.
5657	virtual bool isExecutedInAlignedRegion(Attributor &A,
5658	const Instruction &I) const = 0;
5659
5660	virtual ExecutionDomainTy getExecutionDomain(const BasicBlock &) const = 0;
5661	/// Return the execution domain with which the call \p CB is entered and the
5662	/// one with which it is left.
5663	virtual std::pair<ExecutionDomainTy, ExecutionDomainTy>
5664	getExecutionDomain(const CallBase &CB) const = 0;
5665	virtual ExecutionDomainTy getFunctionExecutionDomain() const = 0;
5666
5667	/// Helper function to determine if \p FI is a no-op given the information
5668	/// about its execution from \p ExecDomainAA.
5669	virtual bool isNoOpFence(const FenceInst &FI) const = 0;
5670
5671	/// This function should return true if the type of the \p AA is
5672	/// AAExecutionDomain.
5673	static bool classof(const AbstractAttribute *AA) {
5674	return (AA->getIdAddr() == &ID);
5675	}
5676
5677	/// Unique ID (due to the unique address)
5678	static const char ID;
5679	};
5680
5681	/// An abstract Attribute for computing reachability between functions.
5682	struct AAInterFnReachability
5683	: public StateWrapper<BooleanState, AbstractAttribute> {
5684	using Base = StateWrapper<BooleanState, AbstractAttribute>;
5685
5686	AAInterFnReachability(const IRPosition &IRP, Attributor &A) : Base(IRP) {}
5687
5688	/// If the function represented by this possition can reach \p Fn.
5689	bool canReach(Attributor &A, const Function &Fn) const {
5690	Function *Scope = getAnchorScope();
5691	if (!Scope || Scope->isDeclaration())
5692	return true;
5693	return instructionCanReach(A, Inst: Scope->getEntryBlock().front(), Fn);
5694	}
5695
5696	/// Can \p Inst reach \p Fn.
5697	/// See also AA::isPotentiallyReachable.
5698	virtual bool instructionCanReach(
5699	Attributor &A, const Instruction &Inst, const Function &Fn,
5700	const AA::InstExclusionSetTy *ExclusionSet = nullptr) const = 0;
5701
5702	/// Create an abstract attribute view for the position \p IRP.
5703	static AAInterFnReachability &createForPosition(const IRPosition &IRP,
5704	Attributor &A);
5705
5706	/// See AbstractAttribute::getName()
5707	const std::string getName() const override { return "AAInterFnReachability"; }
5708
5709	/// See AbstractAttribute::getIdAddr()
5710	const char *getIdAddr() const override { return &ID; }
5711
5712	/// This function should return true if the type of the \p AA is AACallEdges.
5713	static bool classof(const AbstractAttribute *AA) {
5714	return (AA->getIdAddr() == &ID);
5715	}
5716
5717	/// Unique ID (due to the unique address)
5718	static const char ID;
5719	};
5720
5721	/// An abstract Attribute for determining the necessity of the convergent
5722	/// attribute.
5723	struct AANonConvergent : public StateWrapper<BooleanState, AbstractAttribute> {
5724	using Base = StateWrapper<BooleanState, AbstractAttribute>;
5725
5726	AANonConvergent(const IRPosition &IRP, Attributor &A) : Base(IRP) {}
5727
5728	/// Create an abstract attribute view for the position \p IRP.
5729	static AANonConvergent &createForPosition(const IRPosition &IRP,
5730	Attributor &A);
5731
5732	/// Return true if "non-convergent" is assumed.
5733	bool isAssumedNotConvergent() const { return getAssumed(); }
5734
5735	/// Return true if "non-convergent" is known.
5736	bool isKnownNotConvergent() const { return getKnown(); }
5737
5738	/// See AbstractAttribute::getName()
5739	const std::string getName() const override { return "AANonConvergent"; }
5740
5741	/// See AbstractAttribute::getIdAddr()
5742	const char *getIdAddr() const override { return &ID; }
5743
5744	/// This function should return true if the type of the \p AA is
5745	/// AANonConvergent.
5746	static bool classof(const AbstractAttribute *AA) {
5747	return (AA->getIdAddr() == &ID);
5748	}
5749
5750	/// Unique ID (due to the unique address)
5751	static const char ID;
5752	};
5753
5754	/// An abstract interface for struct information.
5755	struct AAPointerInfo : public AbstractAttribute {
5756	AAPointerInfo(const IRPosition &IRP) : AbstractAttribute(IRP) {}
5757
5758	/// See AbstractAttribute::isValidIRPositionForInit
5759	static bool isValidIRPositionForInit(Attributor &A, const IRPosition &IRP) {
5760	if (!IRP.getAssociatedType()->isPtrOrPtrVectorTy())
5761	return false;
5762	return AbstractAttribute::isValidIRPositionForInit(A, IRP);
5763	}
5764
5765	enum AccessKind {
5766	// First two bits to distinguish may and must accesses.
5767	AK_MUST = 1 << 0,
5768	AK_MAY = 1 << 1,
5769
5770	// Then two bits for read and write. These are not exclusive.
5771	AK_R = 1 << 2,
5772	AK_W = 1 << 3,
5773	AK_RW = AK_R | AK_W,
5774
5775	// One special case for assumptions about memory content. These
5776	// are neither reads nor writes. They are however always modeled
5777	// as read to avoid using them for write removal.
5778	AK_ASSUMPTION = (1 << 4) | AK_MUST,
5779
5780	// Helper for easy access.
5781	AK_MAY_READ = AK_MAY | AK_R,
5782	AK_MAY_WRITE = AK_MAY | AK_W,
5783	AK_MAY_READ_WRITE = AK_MAY | AK_R | AK_W,
5784	AK_MUST_READ = AK_MUST | AK_R,
5785	AK_MUST_WRITE = AK_MUST | AK_W,
5786	AK_MUST_READ_WRITE = AK_MUST | AK_R | AK_W,
5787	};
5788
5789	/// A container for a list of ranges.
5790	struct RangeList {
5791	// The set of ranges rarely contains more than one element, and is unlikely
5792	// to contain more than say four elements. So we find the middle-ground with
5793	// a sorted vector. This avoids hard-coding a rarely used number like "four"
5794	// into every instance of a SmallSet.
5795	using RangeTy = AA::RangeTy;
5796	using VecTy = SmallVector<RangeTy>;
5797	using iterator = VecTy::iterator;
5798	using const_iterator = VecTy::const_iterator;
5799	VecTy Ranges;
5800
5801	RangeList(const RangeTy &R) { Ranges.push_back(Elt: R); }
5802	RangeList(ArrayRef<int64_t> Offsets, int64_t Size) {
5803	Ranges.reserve(N: Offsets.size());
5804	for (unsigned i = 0, e = Offsets.size(); i != e; ++i) {
5805	assert(((i + 1 == e) || Offsets[i] < Offsets[i + 1]) &&
5806	"Expected strictly ascending offsets.");
5807	Ranges.emplace_back(Args: Offsets[i], Args&: Size);
5808	}
5809	}
5810	RangeList() = default;
5811
5812	iterator begin() { return Ranges.begin(); }
5813	iterator end() { return Ranges.end(); }
5814	const_iterator begin() const { return Ranges.begin(); }
5815	const_iterator end() const { return Ranges.end(); }
5816
5817	// Helpers required for std::set_difference
5818	using value_type = RangeTy;
5819	void push_back(const RangeTy &R) {
5820	assert((Ranges.empty() || RangeTy::OffsetLessThan(Ranges.back(), R)) &&
5821	"Ensure the last element is the greatest.");
5822	Ranges.push_back(Elt: R);
5823	}
5824
5825	/// Copy ranges from \p L that are not in \p R, into \p D.
5826	static void set_difference(const RangeList &L, const RangeList &R,
5827	RangeList &D) {
5828	std::set_difference(first1: L.begin(), last1: L.end(), first2: R.begin(), last2: R.end(),
5829	result: std::back_inserter(x&: D), comp: RangeTy::OffsetLessThan);
5830	}
5831
5832	unsigned size() const { return Ranges.size(); }
5833
5834	bool operator==(const RangeList &OI) const { return Ranges == OI.Ranges; }
5835
5836	/// Merge the ranges in \p RHS into the current ranges.
5837	/// - Merging a list of unknown ranges makes the current list unknown.
5838	/// - Ranges with the same offset are merged according to RangeTy::operator&
5839	/// \return true if the current RangeList changed.
5840	bool merge(const RangeList &RHS) {
5841	if (isUnknown())
5842	return false;
5843	if (RHS.isUnknown()) {
5844	setUnknown();
5845	return true;
5846	}
5847
5848	if (Ranges.empty()) {
5849	Ranges = RHS.Ranges;
5850	return true;
5851	}
5852
5853	bool Changed = false;
5854	auto LPos = Ranges.begin();
5855	for (auto &R : RHS.Ranges) {
5856	auto Result = insert(Pos: LPos, R);
5857	if (isUnknown())
5858	return true;
5859	LPos = Result.first;
5860	Changed |= Result.second;
5861	}
5862	return Changed;
5863	}
5864
5865	/// Insert \p R at the given iterator \p Pos, and merge if necessary.
5866	///
5867	/// This assumes that all ranges before \p Pos are OffsetLessThan \p R, and
5868	/// then maintains the sorted order for the suffix list.
5869	///
5870	/// \return The place of insertion and true iff anything changed.
5871	std::pair<iterator, bool> insert(iterator Pos, const RangeTy &R) {
5872	if (isUnknown())
5873	return std::make_pair(x: Ranges.begin(), y: false);
5874	if (R.offsetOrSizeAreUnknown()) {
5875	return std::make_pair(x: setUnknown(), y: true);
5876	}
5877
5878	// Maintain this as a sorted vector of unique entries.
5879	auto LB = std::lower_bound(first: Pos, last: Ranges.end(), val: R, comp: RangeTy::OffsetLessThan);
5880	if (LB == Ranges.end() || LB->Offset != R.Offset)
5881	return std::make_pair(x: Ranges.insert(I: LB, Elt: R), y: true);
5882	bool Changed = *LB != R;
5883	*LB &= R;
5884	if (LB->offsetOrSizeAreUnknown())
5885	return std::make_pair(x: setUnknown(), y: true);
5886	return std::make_pair(x&: LB, y&: Changed);
5887	}
5888
5889	/// Insert the given range \p R, maintaining sorted order.
5890	///
5891	/// \return The place of insertion and true iff anything changed.
5892	std::pair<iterator, bool> insert(const RangeTy &R) {
5893	return insert(Pos: Ranges.begin(), R);
5894	}
5895
5896	/// Add the increment \p Inc to the offset of every range.
5897	void addToAllOffsets(int64_t Inc) {
5898	assert(!isUnassigned() &&
5899	"Cannot increment if the offset is not yet computed!");
5900	if (isUnknown())
5901	return;
5902	for (auto &R : Ranges) {
5903	R.Offset += Inc;
5904	}
5905	}
5906
5907	/// Return true iff there is exactly one range and it is known.
5908	bool isUnique() const {
5909	return Ranges.size() == 1 && !Ranges.front().offsetOrSizeAreUnknown();
5910	}
5911
5912	/// Return the unique range, assuming it exists.
5913	const RangeTy &getUnique() const {
5914	assert(isUnique() && "No unique range to return!");
5915	return Ranges.front();
5916	}
5917
5918	/// Return true iff the list contains an unknown range.
5919	bool isUnknown() const {
5920	if (isUnassigned())
5921	return false;
5922	if (Ranges.front().offsetOrSizeAreUnknown()) {
5923	assert(Ranges.size() == 1 && "Unknown is a singleton range.");
5924	return true;
5925	}
5926	return false;
5927	}
5928
5929	/// Discard all ranges and insert a single unknown range.
5930	iterator setUnknown() {
5931	Ranges.clear();
5932	Ranges.push_back(Elt: RangeTy::getUnknown());
5933	return Ranges.begin();
5934	}
5935
5936	/// Return true if no ranges have been inserted.
5937	bool isUnassigned() const { return Ranges.size() == 0; }
5938	};
5939
5940	/// An access description.
5941	struct Access {
5942	Access(Instruction *I, int64_t Offset, int64_t Size,
5943	std::optional<Value *> Content, AccessKind Kind, Type *Ty)
5944	: LocalI(I), RemoteI(I), Content(Content), Ranges(Offset, Size),
5945	Kind(Kind), Ty(Ty) {
5946	verify();
5947	}
5948	Access(Instruction *LocalI, Instruction *RemoteI, const RangeList &Ranges,
5949	std::optional<Value *> Content, AccessKind K, Type *Ty)
5950	: LocalI(LocalI), RemoteI(RemoteI), Content(Content), Ranges(Ranges),
5951	Kind(K), Ty(Ty) {
5952	if (Ranges.size() > 1) {
5953	Kind = AccessKind(Kind | AK_MAY);
5954	Kind = AccessKind(Kind & ~AK_MUST);
5955	}
5956	verify();
5957	}
5958	Access(Instruction *LocalI, Instruction *RemoteI, int64_t Offset,
5959	int64_t Size, std::optional<Value *> Content, AccessKind Kind,
5960	Type *Ty)
5961	: LocalI(LocalI), RemoteI(RemoteI), Content(Content),
5962	Ranges(Offset, Size), Kind(Kind), Ty(Ty) {
5963	verify();
5964	}
5965	Access(const Access &Other) = default;
5966
5967	Access &operator=(const Access &Other) = default;
5968	bool operator==(const Access &R) const {
5969	return LocalI == R.LocalI && RemoteI == R.RemoteI && Ranges == R.Ranges &&
5970	Content == R.Content && Kind == R.Kind;
5971	}
5972	bool operator!=(const Access &R) const { return !(*this == R); }
5973
5974	Access &operator&=(const Access &R) {
5975	assert(RemoteI == R.RemoteI && "Expected same instruction!");
5976	assert(LocalI == R.LocalI && "Expected same instruction!");
5977
5978	// Note that every Access object corresponds to a unique Value, and only
5979	// accesses to the same Value are merged. Hence we assume that all ranges
5980	// are the same size. If ranges can be different size, then the contents
5981	// must be dropped.
5982	Ranges.merge(RHS: R.Ranges);
5983	Content =
5984	AA::combineOptionalValuesInAAValueLatice(A: Content, B: R.Content, Ty);
5985
5986	// Combine the access kind, which results in a bitwise union.
5987	// If there is more than one range, then this must be a MAY.
5988	// If we combine a may and a must access we clear the must bit.
5989	Kind = AccessKind(Kind | R.Kind);
5990	if ((Kind & AK_MAY) || Ranges.size() > 1) {
5991	Kind = AccessKind(Kind | AK_MAY);
5992	Kind = AccessKind(Kind & ~AK_MUST);
5993	}
5994	verify();
5995	return *this;
5996	}
5997
5998	void verify() {
5999	assert(isMustAccess() + isMayAccess() == 1 &&
6000	"Expect must or may access, not both.");
6001	assert(isAssumption() + isWrite() <= 1 &&
6002	"Expect assumption access or write access, never both.");
6003	assert((isMayAccess() || Ranges.size() == 1) &&
6004	"Cannot be a must access if there are multiple ranges.");
6005	}
6006
6007	/// Return the access kind.
6008	AccessKind getKind() const { return Kind; }
6009
6010	/// Return true if this is a read access.
6011	bool isRead() const { return Kind & AK_R; }
6012
6013	/// Return true if this is a write access.
6014	bool isWrite() const { return Kind & AK_W; }
6015
6016	/// Return true if this is a write access.
6017	bool isWriteOrAssumption() const { return isWrite() || isAssumption(); }
6018
6019	/// Return true if this is an assumption access.
6020	bool isAssumption() const { return Kind == AK_ASSUMPTION; }
6021
6022	bool isMustAccess() const {
6023	bool MustAccess = Kind & AK_MUST;
6024	assert((!MustAccess || Ranges.size() < 2) &&
6025	"Cannot be a must access if there are multiple ranges.");
6026	return MustAccess;
6027	}
6028
6029	bool isMayAccess() const {
6030	bool MayAccess = Kind & AK_MAY;
6031	assert((MayAccess || Ranges.size() < 2) &&
6032	"Cannot be a must access if there are multiple ranges.");
6033	return MayAccess;
6034	}
6035
6036	/// Return the instruction that causes the access with respect to the local
6037	/// scope of the associated attribute.
6038	Instruction *getLocalInst() const { return LocalI; }
6039
6040	/// Return the actual instruction that causes the access.
6041	Instruction *getRemoteInst() const { return RemoteI; }
6042
6043	/// Return true if the value written is not known yet.
6044	bool isWrittenValueYetUndetermined() const { return !Content; }
6045
6046	/// Return true if the value written cannot be determined at all.
6047	bool isWrittenValueUnknown() const {
6048	return Content.has_value() && !*Content;
6049	}
6050
6051	/// Set the value written to nullptr, i.e., unknown.
6052	void setWrittenValueUnknown() { Content = nullptr; }
6053
6054	/// Return the type associated with the access, if known.
6055	Type *getType() const { return Ty; }
6056
6057	/// Return the value writen, if any.
6058	Value *getWrittenValue() const {
6059	assert(!isWrittenValueYetUndetermined() &&
6060	"Value needs to be determined before accessing it.");
6061	return *Content;
6062	}
6063
6064	/// Return the written value which can be `llvm::null` if it is not yet
6065	/// determined.
6066	std::optional<Value *> getContent() const { return Content; }
6067
6068	bool hasUniqueRange() const { return Ranges.isUnique(); }
6069	const AA::RangeTy &getUniqueRange() const { return Ranges.getUnique(); }
6070
6071	/// Add a range accessed by this Access.
6072	///
6073	/// If there are multiple ranges, then this is a "may access".
6074	void addRange(int64_t Offset, int64_t Size) {
6075	Ranges.insert(R: {Offset, Size});
6076	if (!hasUniqueRange()) {
6077	Kind = AccessKind(Kind | AK_MAY);
6078	Kind = AccessKind(Kind & ~AK_MUST);
6079	}
6080	}
6081
6082	const RangeList &getRanges() const { return Ranges; }
6083
6084	using const_iterator = RangeList::const_iterator;
6085	const_iterator begin() const { return Ranges.begin(); }
6086	const_iterator end() const { return Ranges.end(); }
6087
6088	private:
6089	/// The instruction responsible for the access with respect to the local
6090	/// scope of the associated attribute.
6091	Instruction *LocalI;
6092
6093	/// The instruction responsible for the access.
6094	Instruction *RemoteI;
6095
6096	/// The value written, if any. `std::nullopt` means "not known yet",
6097	/// `nullptr` cannot be determined.
6098	std::optional<Value *> Content;
6099
6100	/// Set of potential ranges accessed from the base pointer.
6101	RangeList Ranges;
6102
6103	/// The access kind, e.g., READ, as bitset (could be more than one).
6104	AccessKind Kind;
6105
6106	/// The type of the content, thus the type read/written, can be null if not
6107	/// available.
6108	Type *Ty;
6109	};
6110
6111	/// Create an abstract attribute view for the position \p IRP.
6112	static AAPointerInfo &createForPosition(const IRPosition &IRP, Attributor &A);
6113
6114	/// See AbstractAttribute::getName()
6115	const std::string getName() const override { return "AAPointerInfo"; }
6116
6117	/// See AbstractAttribute::getIdAddr()
6118	const char *getIdAddr() const override { return &ID; }
6119
6120	using OffsetBinsTy = DenseMap<AA::RangeTy, SmallSet<unsigned, 4>>;
6121	using const_bin_iterator = OffsetBinsTy::const_iterator;
6122	virtual const_bin_iterator begin() const = 0;
6123	virtual const_bin_iterator end() const = 0;
6124	virtual int64_t numOffsetBins() const = 0;
6125
6126	/// Call \p CB on all accesses that might interfere with \p Range and return
6127	/// true if all such accesses were known and the callback returned true for
6128	/// all of them, false otherwise. An access interferes with an offset-size
6129	/// pair if it might read or write that memory region.
6130	virtual bool forallInterferingAccesses(
6131	AA::RangeTy Range, function_ref<bool(const Access &, bool)> CB) const = 0;
6132
6133	/// Call \p CB on all accesses that might interfere with \p I and
6134	/// return true if all such accesses were known and the callback returned true
6135	/// for all of them, false otherwise. In contrast to forallInterferingAccesses
6136	/// this function will perform reasoning to exclude write accesses that cannot
6137	/// affect the load even if they on the surface look as if they would. The
6138	/// flag \p HasBeenWrittenTo will be set to true if we know that \p I does not
6139	/// read the initial value of the underlying memory. If \p SkipCB is given and
6140	/// returns false for a potentially interfering access, that access is not
6141	/// checked for actual interference.
6142	virtual bool forallInterferingAccesses(
6143	Attributor &A, const AbstractAttribute &QueryingAA, Instruction &I,
6144	bool FindInterferingWrites, bool FindInterferingReads,
6145	function_ref<bool(const Access &, bool)> CB, bool &HasBeenWrittenTo,
6146	AA::RangeTy &Range,
6147	function_ref<bool(const Access &)> SkipCB = nullptr) const = 0;
6148
6149	/// This function should return true if the type of the \p AA is AAPointerInfo
6150	static bool classof(const AbstractAttribute *AA) {
6151	return (AA->getIdAddr() == &ID);
6152	}
6153
6154	/// Unique ID (due to the unique address)
6155	static const char ID;
6156	};
6157
6158	raw_ostream &operator<<(raw_ostream &, const AAPointerInfo::Access &);
6159
6160	/// An abstract attribute for getting assumption information.
6161	struct AAAssumptionInfo
6162	: public StateWrapper<SetState<StringRef>, AbstractAttribute,
6163	DenseSet<StringRef>> {
6164	using Base =
6165	StateWrapper<SetState<StringRef>, AbstractAttribute, DenseSet<StringRef>>;
6166
6167	AAAssumptionInfo(const IRPosition &IRP, Attributor &A,
6168	const DenseSet<StringRef> &Known)
6169	: Base(IRP, Known) {}
6170
6171	/// Returns true if the assumption set contains the assumption \p Assumption.
6172	virtual bool hasAssumption(const StringRef Assumption) const = 0;
6173
6174	/// Create an abstract attribute view for the position \p IRP.
6175	static AAAssumptionInfo &createForPosition(const IRPosition &IRP,
6176	Attributor &A);
6177
6178	/// See AbstractAttribute::getName()
6179	const std::string getName() const override { return "AAAssumptionInfo"; }
6180
6181	/// See AbstractAttribute::getIdAddr()
6182	const char *getIdAddr() const override { return &ID; }
6183
6184	/// This function should return true if the type of the \p AA is
6185	/// AAAssumptionInfo
6186	static bool classof(const AbstractAttribute *AA) {
6187	return (AA->getIdAddr() == &ID);
6188	}
6189
6190	/// Unique ID (due to the unique address)
6191	static const char ID;
6192	};
6193
6194	/// An abstract attribute for getting all assumption underlying objects.
6195	struct AAUnderlyingObjects : AbstractAttribute {
6196	AAUnderlyingObjects(const IRPosition &IRP) : AbstractAttribute(IRP) {}
6197
6198	/// See AbstractAttribute::isValidIRPositionForInit
6199	static bool isValidIRPositionForInit(Attributor &A, const IRPosition &IRP) {
6200	if (!IRP.getAssociatedType()->isPtrOrPtrVectorTy())
6201	return false;
6202	return AbstractAttribute::isValidIRPositionForInit(A, IRP);
6203	}
6204
6205	/// See AbstractAttribute::requiresCallersForArgOrFunction
6206	static bool requiresCallersForArgOrFunction() { return true; }
6207
6208	/// Create an abstract attribute biew for the position \p IRP.
6209	static AAUnderlyingObjects &createForPosition(const IRPosition &IRP,
6210	Attributor &A);
6211
6212	/// See AbstractAttribute::getName()
6213	const std::string getName() const override { return "AAUnderlyingObjects"; }
6214
6215	/// See AbstractAttribute::getIdAddr()
6216	const char *getIdAddr() const override { return &ID; }
6217
6218	/// This function should return true if the type of the \p AA is
6219	/// AAUnderlyingObjects.
6220	static bool classof(const AbstractAttribute *AA) {
6221	return (AA->getIdAddr() == &ID);
6222	}
6223
6224	/// Unique ID (due to the unique address)
6225	static const char ID;
6226
6227	/// Check \p Pred on all underlying objects in \p Scope collected so far.
6228	///
6229	/// This method will evaluate \p Pred on all underlying objects in \p Scope
6230	/// collected so far and return true if \p Pred holds on all of them.
6231	virtual bool
6232	forallUnderlyingObjects(function_ref<bool(Value &)> Pred,
6233	AA::ValueScope Scope = AA::Interprocedural) const = 0;
6234	};
6235
6236	/// An abstract interface for address space information.
6237	struct AAAddressSpace : public StateWrapper<BooleanState, AbstractAttribute> {
6238	AAAddressSpace(const IRPosition &IRP, Attributor &A)
6239	: StateWrapper<BooleanState, AbstractAttribute>(IRP) {}
6240
6241	/// See AbstractAttribute::isValidIRPositionForInit
6242	static bool isValidIRPositionForInit(Attributor &A, const IRPosition &IRP) {
6243	if (!IRP.getAssociatedType()->isPtrOrPtrVectorTy())
6244	return false;
6245	return AbstractAttribute::isValidIRPositionForInit(A, IRP);
6246	}
6247
6248	/// See AbstractAttribute::requiresCallersForArgOrFunction
6249	static bool requiresCallersForArgOrFunction() { return true; }
6250
6251	/// Return the address space of the associated value. \p NoAddressSpace is
6252	/// returned if the associated value is dead. This functions is not supposed
6253	/// to be called if the AA is invalid.
6254	virtual int32_t getAddressSpace() const = 0;
6255
6256	/// Create an abstract attribute view for the position \p IRP.
6257	static AAAddressSpace &createForPosition(const IRPosition &IRP,
6258	Attributor &A);
6259
6260	/// See AbstractAttribute::getName()
6261	const std::string getName() const override { return "AAAddressSpace"; }
6262
6263	/// See AbstractAttribute::getIdAddr()
6264	const char *getIdAddr() const override { return &ID; }
6265
6266	/// This function should return true if the type of the \p AA is
6267	/// AAAssumptionInfo
6268	static bool classof(const AbstractAttribute *AA) {
6269	return (AA->getIdAddr() == &ID);
6270	}
6271
6272	// No address space which indicates the associated value is dead.
6273	static const int32_t NoAddressSpace = -1;
6274
6275	/// Unique ID (due to the unique address)
6276	static const char ID;
6277	};
6278
6279	struct AAAllocationInfo : public StateWrapper<BooleanState, AbstractAttribute> {
6280	AAAllocationInfo(const IRPosition &IRP, Attributor &A)
6281	: StateWrapper<BooleanState, AbstractAttribute>(IRP) {}
6282
6283	/// See AbstractAttribute::isValidIRPositionForInit
6284	static bool isValidIRPositionForInit(Attributor &A, const IRPosition &IRP) {
6285	if (!IRP.getAssociatedType()->isPtrOrPtrVectorTy())
6286	return false;
6287	return AbstractAttribute::isValidIRPositionForInit(A, IRP);
6288	}
6289
6290	/// Create an abstract attribute view for the position \p IRP.
6291	static AAAllocationInfo &createForPosition(const IRPosition &IRP,
6292	Attributor &A);
6293
6294	virtual std::optional<TypeSize> getAllocatedSize() const = 0;
6295
6296	/// See AbstractAttribute::getName()
6297	const std::string getName() const override { return "AAAllocationInfo"; }
6298
6299	/// See AbstractAttribute::getIdAddr()
6300	const char *getIdAddr() const override { return &ID; }
6301
6302	/// This function should return true if the type of the \p AA is
6303	/// AAAllocationInfo
6304	static bool classof(const AbstractAttribute *AA) {
6305	return (AA->getIdAddr() == &ID);
6306	}
6307
6308	constexpr static const std::optional<TypeSize> HasNoAllocationSize =
6309	std::optional<TypeSize>(TypeSize(-1, true));
6310
6311	static const char ID;
6312	};
6313
6314	/// An abstract interface for llvm::GlobalValue information interference.
6315	struct AAGlobalValueInfo
6316	: public StateWrapper<BooleanState, AbstractAttribute> {
6317	AAGlobalValueInfo(const IRPosition &IRP, Attributor &A)
6318	: StateWrapper<BooleanState, AbstractAttribute>(IRP) {}
6319
6320	/// See AbstractAttribute::isValidIRPositionForInit
6321	static bool isValidIRPositionForInit(Attributor &A, const IRPosition &IRP) {
6322	if (IRP.getPositionKind() != IRPosition::IRP_FLOAT)
6323	return false;
6324	auto *GV = dyn_cast<GlobalValue>(Val: &IRP.getAnchorValue());
6325	if (!GV)
6326	return false;
6327	return GV->hasLocalLinkage();
6328	}
6329
6330	/// Create an abstract attribute view for the position \p IRP.
6331	static AAGlobalValueInfo &createForPosition(const IRPosition &IRP,
6332	Attributor &A);
6333
6334	/// Return true iff \p U is a potential use of the associated global value.
6335	virtual bool isPotentialUse(const Use &U) const = 0;
6336
6337	/// See AbstractAttribute::getName()
6338	const std::string getName() const override { return "AAGlobalValueInfo"; }
6339
6340	/// See AbstractAttribute::getIdAddr()
6341	const char *getIdAddr() const override { return &ID; }
6342
6343	/// This function should return true if the type of the \p AA is
6344	/// AAGlobalValueInfo
6345	static bool classof(const AbstractAttribute *AA) {
6346	return (AA->getIdAddr() == &ID);
6347	}
6348
6349	/// Unique ID (due to the unique address)
6350	static const char ID;
6351	};
6352
6353	/// An abstract interface for indirect call information interference.
6354	struct AAIndirectCallInfo
6355	: public StateWrapper<BooleanState, AbstractAttribute> {
6356	AAIndirectCallInfo(const IRPosition &IRP, Attributor &A)
6357	: StateWrapper<BooleanState, AbstractAttribute>(IRP) {}
6358
6359	/// See AbstractAttribute::isValidIRPositionForInit
6360	static bool isValidIRPositionForInit(Attributor &A, const IRPosition &IRP) {
6361	if (IRP.getPositionKind() != IRPosition::IRP_CALL_SITE)
6362	return false;
6363	auto *CB = cast<CallBase>(Val: IRP.getCtxI());
6364	return CB->getOpcode() == Instruction::Call && CB->isIndirectCall() &&
6365	!CB->isMustTailCall();
6366	}
6367
6368	/// Create an abstract attribute view for the position \p IRP.
6369	static AAIndirectCallInfo &createForPosition(const IRPosition &IRP,
6370	Attributor &A);
6371
6372	/// Call \CB on each potential callee value and return true if all were known
6373	/// and \p CB returned true on all of them. Otherwise, return false.
6374	virtual bool foreachCallee(function_ref<bool(Function *)> CB) const = 0;
6375
6376	/// See AbstractAttribute::getName()
6377	const std::string getName() const override { return "AAIndirectCallInfo"; }
6378
6379	/// See AbstractAttribute::getIdAddr()
6380	const char *getIdAddr() const override { return &ID; }
6381
6382	/// This function should return true if the type of the \p AA is
6383	/// AAIndirectCallInfo
6384	/// This function should return true if the type of the \p AA is
6385	/// AADenormalFPMath.
6386	static bool classof(const AbstractAttribute *AA) {
6387	return (AA->getIdAddr() == &ID);
6388	}
6389
6390	/// Unique ID (due to the unique address)
6391	static const char ID;
6392	};
6393
6394	/// An abstract Attribute for specializing "dynamic" components of
6395	/// "denormal-fp-math" and "denormal-fp-math-f32" to a known denormal mode.
6396	struct AADenormalFPMath
6397	: public StateWrapper<DenormalFPMathState, AbstractAttribute> {
6398	using Base = StateWrapper<DenormalFPMathState, AbstractAttribute>;
6399
6400	AADenormalFPMath(const IRPosition &IRP, Attributor &A) : Base(IRP) {}
6401
6402	/// Create an abstract attribute view for the position \p IRP.
6403	static AADenormalFPMath &createForPosition(const IRPosition &IRP,
6404	Attributor &A);
6405
6406	/// See AbstractAttribute::getName()
6407	const std::string getName() const override { return "AADenormalFPMath"; }
6408
6409	/// See AbstractAttribute::getIdAddr()
6410	const char *getIdAddr() const override { return &ID; }
6411
6412	/// This function should return true if the type of the \p AA is
6413	/// AADenormalFPMath.
6414	static bool classof(const AbstractAttribute *AA) {
6415	return (AA->getIdAddr() == &ID);
6416	}
6417
6418	/// Unique ID (due to the unique address)
6419	static const char ID;
6420	};
6421
6422	raw_ostream &operator<<(raw_ostream &, const AAPointerInfo::Access &);
6423
6424	/// Run options, used by the pass manager.
6425	enum AttributorRunOption {
6426	NONE = 0,
6427	MODULE = 1 << 0,
6428	CGSCC = 1 << 1,
6429	ALL = MODULE | CGSCC
6430	};
6431
6432	namespace AA {
6433	/// Helper to avoid creating an AA for IR Attributes that might already be set.
6434	template <Attribute::AttrKind AK, typename AAType = AbstractAttribute>
6435	bool hasAssumedIRAttr(Attributor &A, const AbstractAttribute *QueryingAA,
6436	const IRPosition &IRP, DepClassTy DepClass, bool &IsKnown,
6437	bool IgnoreSubsumingPositions = false,
6438	const AAType **AAPtr = nullptr) {
6439	IsKnown = false;
6440	switch (AK) {
6441	#define CASE(ATTRNAME, AANAME, ...) \
6442	case Attribute::ATTRNAME: { \
6443	if (AANAME::isImpliedByIR(A, IRP, AK, IgnoreSubsumingPositions)) \
6444	return IsKnown = true; \
6445	if (!QueryingAA) \
6446	return false; \
6447	const auto *AA = A.getAAFor<AANAME>(*QueryingAA, IRP, DepClass); \
6448	if (AAPtr) \
6449	*AAPtr = reinterpret_cast<const AAType *>(AA); \
6450	if (!AA || !AA->isAssumed(__VA_ARGS__)) \
6451	return false; \
6452	IsKnown = AA->isKnown(__VA_ARGS__); \
6453	return true; \
6454	}
6455	CASE(NoUnwind, AANoUnwind, );
6456	CASE(WillReturn, AAWillReturn, );
6457	CASE(NoFree, AANoFree, );
6458	CASE(NoCapture, AANoCapture, );
6459	CASE(NoRecurse, AANoRecurse, );
6460	CASE(NoReturn, AANoReturn, );
6461	CASE(NoSync, AANoSync, );
6462	CASE(NoAlias, AANoAlias, );
6463	CASE(NonNull, AANonNull, );
6464	CASE(MustProgress, AAMustProgress, );
6465	CASE(NoUndef, AANoUndef, );
6466	CASE(ReadNone, AAMemoryBehavior, AAMemoryBehavior::NO_ACCESSES);
6467	CASE(ReadOnly, AAMemoryBehavior, AAMemoryBehavior::NO_WRITES);
6468	CASE(WriteOnly, AAMemoryBehavior, AAMemoryBehavior::NO_READS);
6469	#undef CASE
6470	default:
6471	llvm_unreachable("hasAssumedIRAttr not available for this attribute kind");
6472	};
6473	}
6474	} // namespace AA
6475
6476	} // end namespace llvm
6477
6478	#endif // LLVM_TRANSFORMS_IPO_ATTRIBUTOR_H
6479