include/swift/SILOptimizer/Utils/LoadStoreOptUtils.h - third_party/swift - Git at Google

 //===--- LoadStoreOptUtils.h ------------------------------------*- C++ -*-===//
 //
 // This source file is part of the Swift.org open source project
 //
 // Copyright (c) 2014 - 2017 Apple Inc. and the Swift project authors
 // Licensed under Apache License v2.0 with Runtime Library Exception
 //
 // See https://swift.org/LICENSE.txt for license information
 // See https://swift.org/CONTRIBUTORS.txt for the list of Swift project authors
 //
 //===----------------------------------------------------------------------===//
 ///
 /// This file defines LSBase, a class containing a SILValue base
 /// and a ProjectionPath. It is used as the base class for LSLocation and
 /// LSValue.
 ///
 /// In the case of LSLocation, the base represents the base of the allocated
 /// objects and the ProjectionPath tells which field in the object the
 /// LSLocation represents.
 ///
 /// In the case of LSValue, the base represents the root of loaded or stored
 /// value it represents. And the ProjectionPath represents the field in the
 /// loaded/store value the LSValue represents.
 ///
 //===----------------------------------------------------------------------===//

 #ifndef SWIFT_SIL_LSBASE_H
 #define SWIFT_SIL_LSBASE_H

 #include "swift/SIL/InstructionUtils.h"
 #include "swift/SIL/Projection.h"
 #include "swift/SILOptimizer/Analysis/AliasAnalysis.h"
 #include "swift/SILOptimizer/Analysis/EscapeAnalysis.h"
 #include "swift/SILOptimizer/Analysis/TypeExpansionAnalysis.h"
 #include "swift/SILOptimizer/Analysis/ValueTracking.h"
 #include "swift/SILOptimizer/Utils/Local.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/Hashing.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/Support/Debug.h"
 #include <utility>

 namespace swift {

 class LSBase;
 class LSLocation;
 class LSValue;

 //===----------------------------------------------------------------------===//
 //                           Load Store Base
 //===----------------------------------------------------------------------===//

 class LSBase {
 public:
   enum KeyKind : uint8_t { Empty = 0, Tombstone, Normal };

 protected:
   /// The base of the object.
   SILValue Base;
   /// Empty key, tombstone key or normal key.
   KeyKind Kind;
   /// The path to reach the accessed field of the object.
   Optional<ProjectionPath> Path;

 public:
   /// Constructors.
   LSBase() : Base(), Kind(Normal) {}
   LSBase(KeyKind Kind) : Base(), Kind(Kind) {}
   LSBase(SILValue B) : Base(B), Kind(Normal) {}
   LSBase(SILValue B, const Optional<ProjectionPath> &P, KeyKind Kind = Normal)
       : Base(B), Kind(Kind), Path(P) {}

   /// Virtual destructor.
   virtual ~LSBase() {}

   /// Copy constructor.
   LSBase(const LSBase &RHS) {
     Base = RHS.Base;
     Kind = RHS.Kind;
     Path = RHS.Path;
   }

   /// Assignment operator.
   LSBase &operator=(const LSBase &RHS) {
     Base = RHS.Base;
     Kind = RHS.Kind;
     Path = RHS.Path;
     return *this;
   }

   /// Getters for LSBase.
   KeyKind getKind() const { return Kind; }
   SILValue getBase() const { return Base; }
   const Optional<ProjectionPath> &getPath() const { return Path; }

   /// Reset the LSBase, i.e. clear base and path.
   void reset() {
     Base = SILValue();
     Kind = Normal;
     Path.reset();
   }

   /// Returns whether the LSBase has been initialized properly.
   virtual bool isValid() const { return Base && Path.hasValue(); }

   /// Returns true if the LSBase has a non-empty projection path.
   bool hasEmptyProjectionPath() const { return !Path.getValue().size(); }

   /// return true if that the two objects have the same base but access different
   /// fields of the base object.
   bool hasNonEmptySymmetricPathDifference(const LSBase &RHS) const {
     const ProjectionPath &P = RHS.Path.getValue();
     return Path.getValue().hasNonEmptySymmetricDifference(P);
   }

   /// Subtract the given path from the ProjectionPath.
   void removePathPrefix(Optional<ProjectionPath> &P) {
     if (!P.hasValue())
       return;
     // Remove prefix does not modify the Path in-place.
     Path = ProjectionPath::removePrefix(Path.getValue(), P.getValue());
   }

   /// Return true if the RHS have identical projection paths.
   ///
   /// If both LSBase have empty paths, they are treated as having
   /// identical projection path.
   bool hasIdenticalProjectionPath(const LSBase &RHS) const {
     // If both Paths have no value, then the 2 LSBases are
     // different.
     if (!Path.hasValue() && !RHS.Path.hasValue())
       return false;
     // If 1 Path has value while the other does not, then the 2
     // LSBases are different.
     if (Path.hasValue() != RHS.Path.hasValue())
       return false;
     // If both Paths are empty, then the 2 LSBases are the same.
     if (Path.getValue().empty() && RHS.Path.getValue().empty())
       return true;
     // If both Paths have different values, then the 2 LSBases are
     // different.
     if (Path.getValue() != RHS.Path.getValue())
       return false;
     // Otherwise, the 2 LSBases are the same.
     return true;
   }

   /// Comparisons.
   bool operator!=(const LSBase &RHS) const {
     return !(*this == RHS);
   }
   bool operator==(const LSBase &RHS) const {
     // If type is not the same, then LSBases different.
     if (Kind != RHS.Kind)
       return false;
     // Return true if this is a Tombstone or Empty.
     if (Kind == Empty || Kind == Tombstone)
       return true;
     // If Base is different, then LSBases different.
     if (Base != RHS.Base)
       return false;
     // If the projection paths are different, then LSBases are
     // different.
     if (!hasIdenticalProjectionPath(RHS))
       return false;
     // These LSBases represent the same memory location.
     return true;
   }

   /// Print the LSBase.
   virtual void print(llvm::raw_ostream &os, SILModule *Mod) {
     os << Base;
     Path.getValue().print(os, *Mod);
   }

   virtual void dump(SILModule *Mod) { print(llvm::dbgs(), Mod); }
 };

 static inline llvm::hash_code hash_value(const LSBase &S) {
   const SILValue Base = S.getBase();
   const Optional<ProjectionPath> &Path = S.getPath();
   llvm::hash_code HC = llvm::hash_combine(Base.getOpaqueValue());
   if (!Path.hasValue())
     return HC;
   return llvm::hash_combine(HC, hash_value(Path.getValue()));
 }

 //===----------------------------------------------------------------------===//
 //                            Load Store Value
 //===----------------------------------------------------------------------===//
 using LSLocationValueMap = llvm::DenseMap<LSLocation, LSValue>;
 using LSValueList = llvm::SmallVector<LSValue, 8>;
 using LSValueIndexMap = llvm::SmallDenseMap<LSValue, unsigned, 32>;
 using ValueTableMap = llvm::SmallMapVector<unsigned, unsigned, 8>;

 /// A LSValue is an abstraction of an object field value in program. It
 /// consists of a base that is the tracked SILValue, and a projection path to
 /// the represented field.
 class LSValue : public LSBase {
   /// If this is a covering value, we need to go to each predecessor to
   /// materialize the value.
   bool CoveringValue;
 public:
   /// Constructors.
   LSValue() : LSBase(), CoveringValue(false) {}
   LSValue(KeyKind Kind) : LSBase(Kind), CoveringValue(false) {}
   LSValue(bool CSVal) : LSBase(Normal), CoveringValue(CSVal) {}
   LSValue(SILValue B, const ProjectionPath &P)
       : LSBase(B, P), CoveringValue(false) {}

   /// Copy constructor.
   LSValue(const LSValue &RHS) : LSBase(RHS) {
     CoveringValue = RHS.CoveringValue;
   }

   /// Assignment operator.
   LSValue &operator=(const LSValue &RHS) {
     LSBase::operator=(RHS);
     CoveringValue = RHS.CoveringValue;
     return *this;
   }

   /// Comparisons.
   bool operator!=(const LSValue &RHS) const { return !(*this == RHS); }
   bool operator==(const LSValue &RHS) const {
     if (CoveringValue && RHS.isCoveringValue())
       return true;
     if (CoveringValue != RHS.isCoveringValue())
       return false;
     return LSBase::operator==(RHS);
   }

   /// Returns whether the LSValue has been initialized properly.
   bool isValid() const {
     if (CoveringValue)
       return true;
     return LSBase::isValid();
   }

   /// Take the last level projection off. Return the modified LSValue.
   LSValue &stripLastLevelProjection() {
     Path.getValue().pop_back();
     return *this;
   }

   /// Returns true if this LSValue is a covering value.
   bool isCoveringValue() const { return CoveringValue; }

   /// Materialize the SILValue that this LSValue represents.
   ///
   /// In the case where we have a single value this can be materialized by
   /// applying Path to the Base.
   SILValue materialize(SILInstruction *Inst) {
     if (CoveringValue)
       return SILValue();
     return Path.getValue().createExtract(Base, Inst, true);
   }

   void print(llvm::raw_ostream &os, SILModule *Mod) {
     if (CoveringValue) {
       os << "Covering Value";
       return;
     }
     LSBase::print(os, Mod);
   }

   /// Expand this SILValue to all individual fields it contains.
   static void expand(SILValue Base, SILModule *Mod, LSValueList &Vals,
                      TypeExpansionAnalysis *TE);

   /// Given a memory location and a map between the expansions of the location
   /// and their corresponding values, try to come up with a single SILValue this
   /// location holds. This may involve extracting and aggregating available
   /// values.
   static void reduceInner(LSLocation &B, SILModule *M, LSLocationValueMap &Vals,
                           SILInstruction *InsertPt);
   static SILValue reduce(LSLocation &B, SILModule *M, LSLocationValueMap &Vals,
                          SILInstruction *InsertPt);
 };

 static inline llvm::hash_code hash_value(const LSValue &V) {
   llvm::hash_code HC = llvm::hash_combine(V.isCoveringValue());
   if (V.isCoveringValue())
     return HC;
   return llvm::hash_combine(HC, hash_value((LSBase)V));
 }

 //===----------------------------------------------------------------------===//
 //                            Load Store Location
 //===----------------------------------------------------------------------===//
 using LSLocationSet = llvm::DenseSet<LSLocation>;
 using LSLocationList = llvm::SmallVector<LSLocation, 8>;
 using LSLocationIndexMap = llvm::SmallDenseMap<LSLocation, unsigned, 32>;
 using LSLocationBaseMap = llvm::DenseMap<SILValue, LSLocation>;

 /// This class represents a field in an allocated object. It consists of a
 /// base that is the tracked SILValue, and a projection path to the
 /// represented field.
 class LSLocation : public LSBase {
 public:
   /// Constructors.
   LSLocation() {}
   LSLocation(SILValue B, const Optional<ProjectionPath> &P, KeyKind K = Normal)
       : LSBase(B, P, K) {}
   LSLocation(KeyKind Kind) : LSBase(Kind) {}
   /// Use the concatenation of the 2 ProjectionPaths as the Path.
   LSLocation(SILValue B, const ProjectionPath &BP, const ProjectionPath &AP)
       : LSBase(B) {
     ProjectionPath P((*Base).getType());
     P.append(BP);
     P.append(AP);
     Path = P;
   }

   /// Initialize a location with a new set of base, projectionpath and kind.
   void init(SILValue B, const Optional<ProjectionPath> &P, KeyKind K= Normal) {
     Base = B;
     Path = P;
     Kind = K;
   }

   /// Copy constructor.
   LSLocation(const LSLocation &RHS) : LSBase(RHS) {}

   /// Assignment operator.
   LSLocation &operator=(const LSLocation &RHS) {
     LSBase::operator=(RHS);
     return *this;
   }

   /// Returns the type of the object the LSLocation represents.
   SILType getType(SILModule *M) {
     return Path.getValue().getMostDerivedType(*M);
   }

   /// Get the first level locations based on this location's first level
   /// projection.
   void getNextLevelLSLocations(LSLocationList &Locs, SILModule *Mod);

   /// Check whether the 2 LSLocations may alias each other or not.
   bool isMayAliasLSLocation(const LSLocation &RHS, AliasAnalysis *AA);

   /// Check whether the 2 LSLocations must alias each other or not.
   bool isMustAliasLSLocation(const LSLocation &RHS, AliasAnalysis *AA);

   /// Check whether the LSLocation can escape the current function.
   bool isNonEscapingLocalLSLocation(SILFunction *Fn, EscapeAnalysis *EA);

   /// Expand this location to all individual fields it contains.
   ///
   /// In SIL, we can have a store to an aggregate and loads from its individual
   /// fields. Therefore, we expand all the operations on aggregates onto
   /// individual fields and process them separately.
   static void expand(LSLocation Base, SILModule *Mod, LSLocationList &Locs,
                      TypeExpansionAnalysis *TE);

   /// Given a set of locations derived from the same base, try to merge/reduce
   /// them into smallest number of LSLocations possible.
   static bool reduce(LSLocation Base, SILModule *Mod, LSLocationSet &Locs);

   /// Enumerate the given Mem LSLocation.
   static void enumerateLSLocation(SILModule *M, SILValue Mem,
                                   std::vector<LSLocation> &LSLocationVault,
                                   LSLocationIndexMap &LocToBit,
                                   LSLocationBaseMap &BaseToLoc,
                                   TypeExpansionAnalysis *TE);

   /// Enumerate all the locations in the function.
   static void enumerateLSLocations(SILFunction &F,
                                    std::vector<LSLocation> &LSLocationVault,
                                    LSLocationIndexMap &LocToBit,
                                    LSLocationBaseMap &BaseToLoc,
                                    TypeExpansionAnalysis *TE,
                                    std::pair<int, int> &LSCount);
 };

 static inline llvm::hash_code hash_value(const LSLocation &L) {
   return llvm::hash_combine(hash_value((LSBase)L));
 }

 } // end swift namespace

 /// LSLocation and LSValue are used in DenseMap.
 namespace llvm {
 using swift::LSBase;
 using swift::LSLocation;
 using swift::LSValue;

 template <> struct DenseMapInfo<LSValue> {
   static inline LSValue getEmptyKey() {
     return LSValue(LSBase::Empty);
   }
   static inline LSValue getTombstoneKey() {
     return LSValue(LSBase::Tombstone);
   }
   static inline unsigned getHashValue(const LSValue &Val) {
     return hash_value(Val);
   }
   static bool isEqual(const LSValue &LHS, const LSValue &RHS) {
     return LHS == RHS;
   }
 };

 template <> struct DenseMapInfo<LSLocation> {
   static inline LSLocation getEmptyKey() {
     return LSLocation(LSBase::Empty);
   }
   static inline LSLocation getTombstoneKey() {
     return LSLocation(LSBase::Tombstone);
   }
   static inline unsigned getHashValue(const LSLocation &Loc) {
     return hash_value(Loc);
   }
   static bool isEqual(const LSLocation &LHS, const LSLocation &RHS) {
     return LHS == RHS;
   }
 };

 } // namespace llvm

 #endif // SWIFT_SIL_LSBASE_H
	//===--- LoadStoreOptUtils.h ------------------------------------- C++ --===//
	//
	// This source file is part of the Swift.org open source project
	//
	// Copyright (c) 2014 - 2017 Apple Inc. and the Swift project authors
	// Licensed under Apache License v2.0 with Runtime Library Exception
	//
	// See https://swift.org/LICENSE.txt for license information
	// See https://swift.org/CONTRIBUTORS.txt for the list of Swift project authors
	//
	//===----------------------------------------------------------------------===//
	///
	/// This file defines LSBase, a class containing a SILValue base
	/// and a ProjectionPath. It is used as the base class for LSLocation and
	/// LSValue.
	///
	/// In the case of LSLocation, the base represents the base of the allocated
	/// objects and the ProjectionPath tells which field in the object the
	/// LSLocation represents.
	///
	/// In the case of LSValue, the base represents the root of loaded or stored
	/// value it represents. And the ProjectionPath represents the field in the
	/// loaded/store value the LSValue represents.
	///
	//===----------------------------------------------------------------------===//

	#ifndef SWIFT_SIL_LSBASE_H
	#define SWIFT_SIL_LSBASE_H

	#include "swift/SIL/InstructionUtils.h"
	#include "swift/SIL/Projection.h"
	#include "swift/SILOptimizer/Analysis/AliasAnalysis.h"
	#include "swift/SILOptimizer/Analysis/EscapeAnalysis.h"
	#include "swift/SILOptimizer/Analysis/TypeExpansionAnalysis.h"
	#include "swift/SILOptimizer/Analysis/ValueTracking.h"
	#include "swift/SILOptimizer/Utils/Local.h"
	#include "llvm/ADT/DenseMap.h"
	#include "llvm/ADT/DenseSet.h"
	#include "llvm/ADT/Hashing.h"
	#include "llvm/ADT/SmallVector.h"
	#include "llvm/Support/Debug.h"
	#include <utility>

	namespace swift {

	class LSBase;
	class LSLocation;
	class LSValue;

	//===----------------------------------------------------------------------===//
	// Load Store Base
	//===----------------------------------------------------------------------===//

	class LSBase {
	public:
	enum KeyKind : uint8_t { Empty = 0, Tombstone, Normal };

	protected:
	/// The base of the object.
	SILValue Base;
	/// Empty key, tombstone key or normal key.
	KeyKind Kind;
	/// The path to reach the accessed field of the object.
	Optional<ProjectionPath> Path;

	public:
	/// Constructors.
	LSBase() : Base(), Kind(Normal) {}
	LSBase(KeyKind Kind) : Base(), Kind(Kind) {}
	LSBase(SILValue B) : Base(B), Kind(Normal) {}
	LSBase(SILValue B, const Optional<ProjectionPath> &P, KeyKind Kind = Normal)
	: Base(B), Kind(Kind), Path(P) {}

	/// Virtual destructor.
	virtual ~LSBase() {}

	/// Copy constructor.
	LSBase(const LSBase &RHS) {
	Base = RHS.Base;
	Kind = RHS.Kind;
	Path = RHS.Path;
	}

	/// Assignment operator.
	LSBase &operator=(const LSBase &RHS) {
	Base = RHS.Base;
	Kind = RHS.Kind;
	Path = RHS.Path;
	return *this;
	}

	/// Getters for LSBase.
	KeyKind getKind() const { return Kind; }
	SILValue getBase() const { return Base; }
	const Optional<ProjectionPath> &getPath() const { return Path; }

	/// Reset the LSBase, i.e. clear base and path.
	void reset() {
	Base = SILValue();
	Kind = Normal;
	Path.reset();
	}

	/// Returns whether the LSBase has been initialized properly.
	virtual bool isValid() const { return Base && Path.hasValue(); }

	/// Returns true if the LSBase has a non-empty projection path.
	bool hasEmptyProjectionPath() const { return !Path.getValue().size(); }

	/// return true if that the two objects have the same base but access different
	/// fields of the base object.
	bool hasNonEmptySymmetricPathDifference(const LSBase &RHS) const {
	const ProjectionPath &P = RHS.Path.getValue();
	return Path.getValue().hasNonEmptySymmetricDifference(P);
	}

	/// Subtract the given path from the ProjectionPath.
	void removePathPrefix(Optional<ProjectionPath> &P) {
	if (!P.hasValue())
	return;
	// Remove prefix does not modify the Path in-place.
	Path = ProjectionPath::removePrefix(Path.getValue(), P.getValue());
	}

	/// Return true if the RHS have identical projection paths.
	///
	/// If both LSBase have empty paths, they are treated as having
	/// identical projection path.
	bool hasIdenticalProjectionPath(const LSBase &RHS) const {
	// If both Paths have no value, then the 2 LSBases are
	// different.
	if (!Path.hasValue() && !RHS.Path.hasValue())
	return false;
	// If 1 Path has value while the other does not, then the 2
	// LSBases are different.
	if (Path.hasValue() != RHS.Path.hasValue())
	return false;
	// If both Paths are empty, then the 2 LSBases are the same.
	if (Path.getValue().empty() && RHS.Path.getValue().empty())
	return true;
	// If both Paths have different values, then the 2 LSBases are
	// different.
	if (Path.getValue() != RHS.Path.getValue())
	return false;
	// Otherwise, the 2 LSBases are the same.
	return true;
	}

	/// Comparisons.
	bool operator!=(const LSBase &RHS) const {
	return !(*this == RHS);
	}
	bool operator==(const LSBase &RHS) const {
	// If type is not the same, then LSBases different.
	if (Kind != RHS.Kind)
	return false;
	// Return true if this is a Tombstone or Empty.
	if (Kind == Empty \|\| Kind == Tombstone)
	return true;
	// If Base is different, then LSBases different.
	if (Base != RHS.Base)
	return false;
	// If the projection paths are different, then LSBases are
	// different.
	if (!hasIdenticalProjectionPath(RHS))
	return false;
	// These LSBases represent the same memory location.
	return true;
	}

	/// Print the LSBase.
	virtual void print(llvm::raw_ostream &os, SILModule *Mod) {
	os << Base;
	Path.getValue().print(os, *Mod);
	}

	virtual void dump(SILModule *Mod) { print(llvm::dbgs(), Mod); }
	};

	static inline llvm::hash_code hash_value(const LSBase &S) {
	const SILValue Base = S.getBase();
	const Optional<ProjectionPath> &Path = S.getPath();
	llvm::hash_code HC = llvm::hash_combine(Base.getOpaqueValue());
	if (!Path.hasValue())
	return HC;
	return llvm::hash_combine(HC, hash_value(Path.getValue()));
	}

	//===----------------------------------------------------------------------===//
	// Load Store Value
	//===----------------------------------------------------------------------===//
	using LSLocationValueMap = llvm::DenseMap<LSLocation, LSValue>;
	using LSValueList = llvm::SmallVector<LSValue, 8>;
	using LSValueIndexMap = llvm::SmallDenseMap<LSValue, unsigned, 32>;
	using ValueTableMap = llvm::SmallMapVector<unsigned, unsigned, 8>;

	/// A LSValue is an abstraction of an object field value in program. It
	/// consists of a base that is the tracked SILValue, and a projection path to
	/// the represented field.
	class LSValue : public LSBase {
	/// If this is a covering value, we need to go to each predecessor to
	/// materialize the value.
	bool CoveringValue;
	public:
	/// Constructors.
	LSValue() : LSBase(), CoveringValue(false) {}
	LSValue(KeyKind Kind) : LSBase(Kind), CoveringValue(false) {}
	LSValue(bool CSVal) : LSBase(Normal), CoveringValue(CSVal) {}
	LSValue(SILValue B, const ProjectionPath &P)
	: LSBase(B, P), CoveringValue(false) {}

	/// Copy constructor.
	LSValue(const LSValue &RHS) : LSBase(RHS) {
	CoveringValue = RHS.CoveringValue;
	}

	/// Assignment operator.
	LSValue &operator=(const LSValue &RHS) {
	LSBase::operator=(RHS);
	CoveringValue = RHS.CoveringValue;
	return *this;
	}

	/// Comparisons.
	bool operator!=(const LSValue &RHS) const { return !(*this == RHS); }
	bool operator==(const LSValue &RHS) const {
	if (CoveringValue && RHS.isCoveringValue())
	return true;
	if (CoveringValue != RHS.isCoveringValue())
	return false;
	return LSBase::operator==(RHS);
	}

	/// Returns whether the LSValue has been initialized properly.
	bool isValid() const {
	if (CoveringValue)
	return true;
	return LSBase::isValid();
	}

	/// Take the last level projection off. Return the modified LSValue.
	LSValue &stripLastLevelProjection() {
	Path.getValue().pop_back();
	return *this;
	}

	/// Returns true if this LSValue is a covering value.
	bool isCoveringValue() const { return CoveringValue; }

	/// Materialize the SILValue that this LSValue represents.
	///
	/// In the case where we have a single value this can be materialized by
	/// applying Path to the Base.
	SILValue materialize(SILInstruction *Inst) {
	if (CoveringValue)
	return SILValue();
	return Path.getValue().createExtract(Base, Inst, true);
	}

	void print(llvm::raw_ostream &os, SILModule *Mod) {
	if (CoveringValue) {
	os << "Covering Value";
	return;
	}
	LSBase::print(os, Mod);
	}

	/// Expand this SILValue to all individual fields it contains.
	static void expand(SILValue Base, SILModule *Mod, LSValueList &Vals,
	TypeExpansionAnalysis *TE);

	/// Given a memory location and a map between the expansions of the location
	/// and their corresponding values, try to come up with a single SILValue this
	/// location holds. This may involve extracting and aggregating available
	/// values.
	static void reduceInner(LSLocation &B, SILModule *M, LSLocationValueMap &Vals,
	SILInstruction *InsertPt);
	static SILValue reduce(LSLocation &B, SILModule *M, LSLocationValueMap &Vals,
	SILInstruction *InsertPt);
	};

	static inline llvm::hash_code hash_value(const LSValue &V) {
	llvm::hash_code HC = llvm::hash_combine(V.isCoveringValue());
	if (V.isCoveringValue())
	return HC;
	return llvm::hash_combine(HC, hash_value((LSBase)V));
	}

	//===----------------------------------------------------------------------===//
	// Load Store Location
	//===----------------------------------------------------------------------===//
	using LSLocationSet = llvm::DenseSet<LSLocation>;
	using LSLocationList = llvm::SmallVector<LSLocation, 8>;
	using LSLocationIndexMap = llvm::SmallDenseMap<LSLocation, unsigned, 32>;
	using LSLocationBaseMap = llvm::DenseMap<SILValue, LSLocation>;

	/// This class represents a field in an allocated object. It consists of a
	/// base that is the tracked SILValue, and a projection path to the
	/// represented field.
	class LSLocation : public LSBase {
	public:
	/// Constructors.
	LSLocation() {}
	LSLocation(SILValue B, const Optional<ProjectionPath> &P, KeyKind K = Normal)
	: LSBase(B, P, K) {}
	LSLocation(KeyKind Kind) : LSBase(Kind) {}
	/// Use the concatenation of the 2 ProjectionPaths as the Path.
	LSLocation(SILValue B, const ProjectionPath &BP, const ProjectionPath &AP)
	: LSBase(B) {
	ProjectionPath P((*Base).getType());
	P.append(BP);
	P.append(AP);
	Path = P;
	}

	/// Initialize a location with a new set of base, projectionpath and kind.
	void init(SILValue B, const Optional<ProjectionPath> &P, KeyKind K= Normal) {
	Base = B;
	Path = P;
	Kind = K;
	}

	/// Copy constructor.
	LSLocation(const LSLocation &RHS) : LSBase(RHS) {}

	/// Assignment operator.
	LSLocation &operator=(const LSLocation &RHS) {
	LSBase::operator=(RHS);
	return *this;
	}

	/// Returns the type of the object the LSLocation represents.
	SILType getType(SILModule *M) {
	return Path.getValue().getMostDerivedType(*M);
	}

	/// Get the first level locations based on this location's first level
	/// projection.
	void getNextLevelLSLocations(LSLocationList &Locs, SILModule *Mod);

	/// Check whether the 2 LSLocations may alias each other or not.
	bool isMayAliasLSLocation(const LSLocation &RHS, AliasAnalysis *AA);

	/// Check whether the 2 LSLocations must alias each other or not.
	bool isMustAliasLSLocation(const LSLocation &RHS, AliasAnalysis *AA);

	/// Check whether the LSLocation can escape the current function.
	bool isNonEscapingLocalLSLocation(SILFunction Fn, EscapeAnalysis EA);

	/// Expand this location to all individual fields it contains.
	///
	/// In SIL, we can have a store to an aggregate and loads from its individual
	/// fields. Therefore, we expand all the operations on aggregates onto
	/// individual fields and process them separately.
	static void expand(LSLocation Base, SILModule *Mod, LSLocationList &Locs,
	TypeExpansionAnalysis *TE);

	/// Given a set of locations derived from the same base, try to merge/reduce
	/// them into smallest number of LSLocations possible.
	static bool reduce(LSLocation Base, SILModule *Mod, LSLocationSet &Locs);

	/// Enumerate the given Mem LSLocation.
	static void enumerateLSLocation(SILModule *M, SILValue Mem,
	std::vector<LSLocation> &LSLocationVault,
	LSLocationIndexMap &LocToBit,
	LSLocationBaseMap &BaseToLoc,
	TypeExpansionAnalysis *TE);

	/// Enumerate all the locations in the function.
	static void enumerateLSLocations(SILFunction &F,
	std::vector<LSLocation> &LSLocationVault,
	LSLocationIndexMap &LocToBit,
	LSLocationBaseMap &BaseToLoc,
	TypeExpansionAnalysis *TE,
	std::pair<int, int> &LSCount);
	};

	static inline llvm::hash_code hash_value(const LSLocation &L) {
	return llvm::hash_combine(hash_value((LSBase)L));
	}

	} // end swift namespace

	/// LSLocation and LSValue are used in DenseMap.
	namespace llvm {
	using swift::LSBase;
	using swift::LSLocation;
	using swift::LSValue;

	template <> struct DenseMapInfo<LSValue> {
	static inline LSValue getEmptyKey() {
	return LSValue(LSBase::Empty);
	}
	static inline LSValue getTombstoneKey() {
	return LSValue(LSBase::Tombstone);
	}
	static inline unsigned getHashValue(const LSValue &Val) {
	return hash_value(Val);
	}
	static bool isEqual(const LSValue &LHS, const LSValue &RHS) {
	return LHS == RHS;
	}
	};

	template <> struct DenseMapInfo<LSLocation> {
	static inline LSLocation getEmptyKey() {
	return LSLocation(LSBase::Empty);
	}
	static inline LSLocation getTombstoneKey() {
	return LSLocation(LSBase::Tombstone);
	}
	static inline unsigned getHashValue(const LSLocation &Loc) {
	return hash_value(Loc);
	}
	static bool isEqual(const LSLocation &LHS, const LSLocation &RHS) {
	return LHS == RHS;
	}
	};

	} // namespace llvm

	#endif // SWIFT_SIL_LSBASE_H