This is an archive of the discontinued LLVM Phabricator instance.

Merge TempScopInfo.{cpp|h} into ScopInfo.{cpp|h}
ClosedPublic

Authored by Meinersbur on Sep 8 2015, 7:41 AM.

Download Raw Diff

Details

Reviewers

Meinersbur
grosser
jdoerfert

Summary

This prepares for a series of patches that merges TempScopInfo into ScopInfo to
reduce Polly's code complexity. Only ScopInfo.{cpp|h} will be left thereafter.
Moving the code of TempScopInfo in one commit makes the mains diffs simpler to
understand.

In details, the following classes are intended to be merged:
TempScopInfo into ScopInfo
TempScop into Scop
IRAccess into MemoryAccess

Only moving code, no functional changes intended.

Diff Detail

Event Timeline

Meinersbur updated this revision to Diff 34214.Sep 8 2015, 7:41 AM

Meinersbur retitled this revision from to Merge TempScopInfo.{cpp|h} into ScopInfo.{cpp|h}.

Meinersbur updated this object.

Meinersbur added reviewers: grosser, jdoerfert.

Meinersbur added a project: Restricted Project.

Meinersbur added a subscriber: pollydev.

Herald added a subscriber: sanjoy. · View Herald TranscriptSep 8 2015, 7:41 AM

LGTM

msg-30032-466.dat219 BDownload

Not really needed, as Johannes already OKed this and the following commit,
but these look both good to me.

Tobias

Rebase to r247142

Meinersbur accepted this revision.Sep 10 2015, 7:53 AM

Meinersbur added a reviewer: Meinersbur.

This revision is now accepted and ready to land.Sep 10 2015, 7:53 AM

Committed as r247274

Revision Contents

Path

Size

include/

polly/

ScopInfo.h

267 lines

TempScopInfo.h

lib/

Analysis/

ScopInfo.cpp

368 lines

TempScopInfo.cpp

CMakeLists.txt

1 line

CodeGen/

CodeGeneration.cpp

1 line

IslNodeBuilder.cpp

1 line

Support/

RegisterPasses.cpp

1 line

Diff 34214

include/polly/ScopInfo.h

Show First 20 Lines • Show All 61 Lines • ▼ Show 20 Lines
class IRAccess;		class IRAccess;
class Scop;		class Scop;
class ScopStmt;		class ScopStmt;
class ScopInfo;		class ScopInfo;
class TempScop;		class TempScop;
class Comparison;		class Comparison;
class SCEVAffFunc;		class SCEVAffFunc;

		class Comparison {
		const SCEV *LHS;
		const SCEV *RHS;

		ICmpInst::Predicate Pred;

		public:
		Comparison(const SCEV LHS, const SCEV RHS, ICmpInst::Predicate Pred)
		: LHS(LHS), RHS(RHS), Pred(Pred) {}

		const SCEV *getLHS() const { return LHS; }
		const SCEV *getRHS() const { return RHS; }

		ICmpInst::Predicate getPred() const { return Pred; }
		void print(raw_ostream &OS) const;
		};

		//===---------------------------------------------------------------------===//

		/// Maps from a loop to the affine function expressing its backedge taken count.
		/// The backedge taken count already enough to express iteration domain as we
		/// only allow loops with canonical induction variable.
		/// A canonical induction variable is:
		/// an integer recurrence that starts at 0 and increments by one each time
		/// through the loop.
		typedef std::map<const Loop , const SCEV > LoopBoundMapType;

		typedef std::vector<std::pair<IRAccess, Instruction *>> AccFuncSetType;
		typedef std::map<const BasicBlock *, AccFuncSetType> AccFuncMapType;

/// @brief A class to store information about arrays in the SCoP.		/// @brief A class to store information about arrays in the SCoP.
///		///
/// Objects are accessible via the ScoP, MemoryAccess or the id associated with		/// Objects are accessible via the ScoP, MemoryAccess or the id associated with
/// the MemoryAccess access function.		/// the MemoryAccess access function.
///		///
class ScopArrayInfo {		class ScopArrayInfo {
public:		public:
/// @brief Construct a ScopArrayInfo object.		/// @brief Construct a ScopArrayInfo object.
▲ Show 20 Lines • Show All 101 Lines • ▼ Show 20 Lines	private:

/// @brief The sizes of each dimension as isl_pw_aff.		/// @brief The sizes of each dimension as isl_pw_aff.
SmallVector<isl_pw_aff *, 4> DimensionSizesPw;		SmallVector<isl_pw_aff *, 4> DimensionSizesPw;

/// @brief Is this PHI node specific storage?		/// @brief Is this PHI node specific storage?
bool IsPHI;		bool IsPHI;
};		};


		//===---------------------------------------------------------------------===//
		/// @brief A memory access described by a SCEV expression and the access type.
		class IRAccess {
		public:
		Value *BaseAddress;
		Value *AccessValue;

		const SCEV *Offset;

		// The type of the scev affine function
		enum TypeKind {
		READ = 0x1,
		MUST_WRITE = 0x2,
		MAY_WRITE = 0x3,
		};

		private:
		unsigned ElemBytes;
		TypeKind Type;
		bool IsAffine;

		/// @brief Is this IRAccess modeling special PHI node accesses?
		bool IsPHI;

		public:
		SmallVector<const SCEV *, 4> Subscripts, Sizes;

		/// @brief Create a new IRAccess
		///
		/// @param IsPHI Are we modeling special PHI node accesses?
		explicit IRAccess(TypeKind Type, Value BaseAddress, const SCEV Offset,
		unsigned elemBytes, bool Affine, Value *AccessValue,
		bool IsPHI = false)
		: BaseAddress(BaseAddress), AccessValue(AccessValue), Offset(Offset),
		ElemBytes(elemBytes), Type(Type), IsAffine(Affine), IsPHI(IsPHI) {}

		explicit IRAccess(TypeKind Type, Value BaseAddress, const SCEV Offset,
		unsigned elemBytes, bool Affine,
		SmallVector<const SCEV *, 4> Subscripts,
		SmallVector<const SCEV , 4> Sizes, Value AccessValue)
		: BaseAddress(BaseAddress), AccessValue(AccessValue), Offset(Offset),
		ElemBytes(elemBytes), Type(Type), IsAffine(Affine), IsPHI(false),
		Subscripts(Subscripts), Sizes(Sizes) {}

		enum TypeKind getType() const { return Type; }

		Value *getBase() const { return BaseAddress; }

		Value *getAccessValue() const { return AccessValue; }

		const SCEV *getOffset() const { return Offset; }

		unsigned getElemSizeInBytes() const { return ElemBytes; }

		bool isAffine() const { return IsAffine; }

		bool isRead() const { return Type == READ; }

		bool isWrite() const { return Type == MUST_WRITE; }

		void setMayWrite() { Type = MAY_WRITE; }

		bool isMayWrite() const { return Type == MAY_WRITE; }

		bool isScalar() const { return Subscripts.size() == 0; }

		// @brief Is this IRAccess modeling special PHI node accesses?
		bool isPHI() const { return IsPHI; }

		void print(raw_ostream &OS) const;
		};

/// @brief Represent memory accesses in statements.		/// @brief Represent memory accesses in statements.
class MemoryAccess {		class MemoryAccess {
public:		public:
/// @brief The access type of a memory access		/// @brief The access type of a memory access
///		///
/// There are three kind of access types:		/// There are three kind of access types:
///		///
/// * A read access		/// * A read access
▲ Show 20 Lines • Show All 1,069 Lines • ▼ Show 20 Lines
};		};

/// @brief Print Scop scop to raw_ostream O.		/// @brief Print Scop scop to raw_ostream O.
static inline raw_ostream &operator<<(raw_ostream &O, const Scop &scop) {		static inline raw_ostream &operator<<(raw_ostream &O, const Scop &scop) {
scop.print(O);		scop.print(O);
return O;		return O;
}		}


		//===---------------------------------------------------------------------===//
		/// @brief Scop represent with llvm objects.
		///
		/// A helper class for remembering the parameter number and the max depth in
		/// this Scop, and others context.
		class TempScop {
		// The Region.
		Region &R;

		// Access function of bbs.
		AccFuncMapType &AccFuncMap;

		friend class TempScopInfo;

		explicit TempScop(Region &r, AccFuncMapType &accFuncMap)
		: R(r), AccFuncMap(accFuncMap) {}

		public:
		~TempScop();

		/// @brief Get the maximum Region contained by this Scop.
		///
		/// @return The maximum Region contained by this Scop.
		Region &getMaxRegion() const { return R; }

		/// @brief Get all access functions in a BasicBlock
		///
		/// @param BB The BasicBlock that containing the access functions.
		///
		/// @return All access functions in BB
		///
		AccFuncSetType getAccessFunctions(const BasicBlock BB) {
		AccFuncMapType::iterator at = AccFuncMap.find(BB);
		return at != AccFuncMap.end() ? &(at->second) : 0;
		}
		//@}

		/// @brief Print the Temporary Scop information.
		///
		/// @param OS The output stream the access functions is printed to.
		/// @param SE The ScalarEvolution that help printing Temporary Scop
		/// information.
		/// @param LI The LoopInfo that help printing the access functions.
		void print(raw_ostream &OS, ScalarEvolution SE, LoopInfo LI) const;

		/// @brief Print the access functions and loop bounds in this Scop.
		///
		/// @param OS The output stream the access functions is printed to.
		/// @param SE The ScalarEvolution that help printing the access functions.
		/// @param LI The LoopInfo that help printing the access functions.
		void printDetail(raw_ostream &OS, ScalarEvolution SE, LoopInfo LI,
		const Region *Reg, unsigned ind) const;
		};

		typedef std::map<const Region , TempScop > TempScopMapType;
		//===----------------------------------------------------------------------===//
		/// @brief The Function Pass to extract temporary information for Static control
		/// part in llvm function.
		///
		class TempScopInfo : public RegionPass {
		//===-------------------------------------------------------------------===//
		TempScopInfo(const TempScopInfo &) = delete;
		const TempScopInfo &operator=(const TempScopInfo &) = delete;

		// The ScalarEvolution to help building Scop.
		ScalarEvolution *SE;

		// LoopInfo for information about loops
		LoopInfo *LI;

		// The AliasAnalysis to build AliasSetTracker.
		AliasAnalysis *AA;

		// Valid Regions for Scop
		ScopDetection *SD;

		// Target data for element size computing.
		const DataLayout *TD;

		// Access function of statements (currently BasicBlocks) .
		AccFuncMapType AccFuncMap;

		// Pre-created zero for the scalar accesses, with it we do not need create a
		// zero scev every time when we need it.
		const SCEV *ZeroOffset;

		// The TempScop for this region.
		TempScop *TempScopOfRegion;

		// Clear the context.
		void clear();

		// Build the temprory information of Region R, where R must be a valid part
		// of Scop.
		TempScop *buildTempScop(Region &R);

		/// @brief Build an instance of IRAccess from the Load/Store instruction.
		///
		/// @param Inst The Load/Store instruction that access the memory
		/// @param L The parent loop of the instruction
		/// @param R The region on which we are going to build a TempScop
		/// @param BoxedLoops The set of loops that are overapproximated in @p R.
		///
		/// @return The IRAccess to describe the access function of the
		/// instruction.
		IRAccess buildIRAccess(Instruction Inst, Loop L, Region *R,
		const ScopDetection::BoxedLoopsSetTy *BoxedLoops);

		/// @brief Analyze and extract the cross-BB scalar dependences (or,
		/// dataflow dependencies) of an instruction.
		///
		/// @param Inst The instruction to be analyzed
		/// @param R The SCoP region
		/// @param NonAffineSubRegion The non affine sub-region @p Inst is in.
		///
		/// @return True if the Instruction is used in other BB and a scalar write
		/// Access is required.
		bool buildScalarDependences(Instruction Inst, Region R,
		Region *NonAffineSubRegio);

		/// @brief Create IRAccesses for the given PHI node in the given region.
		///
		/// @param PHI The PHI node to be handled
		/// @param R The SCoP region
		/// @param Functions The access functions of the current BB
		/// @param NonAffineSubRegion The non affine sub-region @p PHI is in.
		void buildPHIAccesses(PHINode *PHI, Region &R, AccFuncSetType &Functions,
		Region *NonAffineSubRegion);

		/// @brief Build the access functions for the subregion @p SR.
		///
		/// @param R The SCoP region.
		/// @param SR A subregion of @p R.
		void buildAccessFunctions(Region &R, Region &SR);

		/// @brief Build the access functions for the basic block @p BB
		///
		/// @param R The SCoP region.
		/// @param BB A basic block in @p R.
		/// @param NonAffineSubRegion The non affine sub-region @p BB is in.
		void buildAccessFunctions(Region &R, BasicBlock &BB,
		Region *NonAffineSubRegion = nullptr);

		public:
		static char ID;
		explicit TempScopInfo() : RegionPass(ID), TempScopOfRegion(nullptr) {}
		~TempScopInfo();

		/// @brief Get the temporay Scop information in LLVM IR for this region.
		///
		/// @return The Scop information in LLVM IR represent.
		TempScop *getTempScop() const;

		/// @name RegionPass interface
		//@{
		virtual void getAnalysisUsage(AnalysisUsage &AU) const;
		virtual void releaseMemory() { clear(); }
		virtual bool runOnRegion(Region *R, RGPassManager &RGM);
		virtual void print(raw_ostream &OS, const Module *) const;
		//@}
		};

///===---------------------------------------------------------------------===//		///===---------------------------------------------------------------------===//
/// @brief Build the Polly IR (Scop and ScopStmt) on a Region.		/// @brief Build the Polly IR (Scop and ScopStmt) on a Region.
///		///
class ScopInfo : public RegionPass {		class ScopInfo : public RegionPass {
//===-------------------------------------------------------------------===//		//===-------------------------------------------------------------------===//
ScopInfo(const ScopInfo &) = delete;		ScopInfo(const ScopInfo &) = delete;
const ScopInfo &operator=(const ScopInfo &) = delete;		const ScopInfo &operator=(const ScopInfo &) = delete;

Show All 35 Lines	public:
}		}
//@}		//@}
};		};

} // end namespace polly		} // end namespace polly

namespace llvm {		namespace llvm {
class PassRegistry;		class PassRegistry;
		void initializeTempScopInfoPass(llvm::PassRegistry &);
void initializeScopInfoPass(llvm::PassRegistry &);		void initializeScopInfoPass(llvm::PassRegistry &);
}		}

#endif		#endif

include/polly/TempScopInfo.h

This file was deleted.

	//===-------- polly/TempScopInfo.h - Extract TempScops ----------- C++ --===//
	//
	// The LLVM Compiler Infrastructure
	//
	// This file is distributed under the University of Illinois Open Source
	// License. See LICENSE.TXT for details.
	//
	//===----------------------------------------------------------------------===//
	//
	// Collect information about the control flow regions detected by the Scop
	// detection, such that this information can be translated info its polyhedral
	// representation.
	//
	//===----------------------------------------------------------------------===//

	#ifndef POLLY_TEMP_SCOP_EXTRACTION_H
	#define POLLY_TEMP_SCOP_EXTRACTION_H

	#include "polly/ScopDetection.h"
	#include "llvm/Analysis/RegionPass.h"
	#include "llvm/IR/Instructions.h"

	namespace llvm {
	class DataLayout;
	}

	using namespace llvm;

	namespace polly {

	//===---------------------------------------------------------------------===//
	/// @brief A memory access described by a SCEV expression and the access type.
	class IRAccess {
	public:
	Value *BaseAddress;
	Value *AccessValue;

	const SCEV *Offset;

	// The type of the scev affine function
	enum TypeKind {
	READ = 0x1,
	MUST_WRITE = 0x2,
	MAY_WRITE = 0x3,
	};

	private:
	unsigned ElemBytes;
	TypeKind Type;
	bool IsAffine;

	/// @brief Is this IRAccess modeling special PHI node accesses?
	bool IsPHI;

	public:
	SmallVector<const SCEV *, 4> Subscripts, Sizes;

	/// @brief Create a new IRAccess
	///
	/// @param IsPHI Are we modeling special PHI node accesses?
	explicit IRAccess(TypeKind Type, Value BaseAddress, const SCEV Offset,
	unsigned elemBytes, bool Affine, Value *AccessValue,
	bool IsPHI = false)
	: BaseAddress(BaseAddress), AccessValue(AccessValue), Offset(Offset),
	ElemBytes(elemBytes), Type(Type), IsAffine(Affine), IsPHI(IsPHI) {}

	explicit IRAccess(TypeKind Type, Value BaseAddress, const SCEV Offset,
	unsigned elemBytes, bool Affine,
	SmallVector<const SCEV *, 4> Subscripts,
	SmallVector<const SCEV , 4> Sizes, Value AccessValue)
	: BaseAddress(BaseAddress), AccessValue(AccessValue), Offset(Offset),
	ElemBytes(elemBytes), Type(Type), IsAffine(Affine), IsPHI(false),
	Subscripts(Subscripts), Sizes(Sizes) {}

	enum TypeKind getType() const { return Type; }

	Value *getBase() const { return BaseAddress; }

	Value *getAccessValue() const { return AccessValue; }

	const SCEV *getOffset() const { return Offset; }

	unsigned getElemSizeInBytes() const { return ElemBytes; }

	bool isAffine() const { return IsAffine; }

	bool isRead() const { return Type == READ; }

	bool isWrite() const { return Type == MUST_WRITE; }

	void setMayWrite() { Type = MAY_WRITE; }

	bool isMayWrite() const { return Type == MAY_WRITE; }

	bool isScalar() const { return Subscripts.size() == 0; }

	// @brief Is this IRAccess modeling special PHI node accesses?
	bool isPHI() const { return IsPHI; }

	void print(raw_ostream &OS) const;
	};

	class Comparison {
	const SCEV *LHS;
	const SCEV *RHS;

	ICmpInst::Predicate Pred;

	public:
	Comparison(const SCEV LHS, const SCEV RHS, ICmpInst::Predicate Pred)
	: LHS(LHS), RHS(RHS), Pred(Pred) {}

	const SCEV *getLHS() const { return LHS; }
	const SCEV *getRHS() const { return RHS; }

	ICmpInst::Predicate getPred() const { return Pred; }
	void print(raw_ostream &OS) const;
	};

	//===---------------------------------------------------------------------===//

	/// Maps from a loop to the affine function expressing its backedge taken count.
	/// The backedge taken count already enough to express iteration domain as we
	/// only allow loops with canonical induction variable.
	/// A canonical induction variable is:
	/// an integer recurrence that starts at 0 and increments by one each time
	/// through the loop.
	typedef std::map<const Loop , const SCEV > LoopBoundMapType;

	typedef std::vector<std::pair<IRAccess, Instruction *>> AccFuncSetType;
	typedef std::map<const BasicBlock *, AccFuncSetType> AccFuncMapType;

	//===---------------------------------------------------------------------===//
	/// @brief Scop represent with llvm objects.
	///
	/// A helper class for remembering the parameter number and the max depth in
	/// this Scop, and others context.
	class TempScop {
	// The Region.
	Region &R;

	// Access function of bbs.
	AccFuncMapType &AccFuncMap;

	friend class TempScopInfo;

	explicit TempScop(Region &r, AccFuncMapType &accFuncMap)
	: R(r), AccFuncMap(accFuncMap) {}

	public:
	~TempScop();

	/// @brief Get the maximum Region contained by this Scop.
	///
	/// @return The maximum Region contained by this Scop.
	Region &getMaxRegion() const { return R; }

	/// @brief Get all access functions in a BasicBlock
	///
	/// @param BB The BasicBlock that containing the access functions.
	///
	/// @return All access functions in BB
	///
	AccFuncSetType getAccessFunctions(const BasicBlock BB) {
	AccFuncMapType::iterator at = AccFuncMap.find(BB);
	return at != AccFuncMap.end() ? &(at->second) : 0;
	}
	//@}

	/// @brief Print the Temporary Scop information.
	///
	/// @param OS The output stream the access functions is printed to.
	/// @param SE The ScalarEvolution that help printing Temporary Scop
	/// information.
	/// @param LI The LoopInfo that help printing the access functions.
	void print(raw_ostream &OS, ScalarEvolution SE, LoopInfo LI) const;

	/// @brief Print the access functions and loop bounds in this Scop.
	///
	/// @param OS The output stream the access functions is printed to.
	/// @param SE The ScalarEvolution that help printing the access functions.
	/// @param LI The LoopInfo that help printing the access functions.
	void printDetail(raw_ostream &OS, ScalarEvolution SE, LoopInfo LI,
	const Region *Reg, unsigned ind) const;
	};

	typedef std::map<const Region , TempScop > TempScopMapType;
	//===----------------------------------------------------------------------===//
	/// @brief The Function Pass to extract temporary information for Static control
	/// part in llvm function.
	///
	class TempScopInfo : public RegionPass {
	//===-------------------------------------------------------------------===//
	TempScopInfo(const TempScopInfo &) = delete;
	const TempScopInfo &operator=(const TempScopInfo &) = delete;

	// The ScalarEvolution to help building Scop.
	ScalarEvolution *SE;

	// LoopInfo for information about loops
	LoopInfo *LI;

	// The AliasAnalysis to build AliasSetTracker.
	AliasAnalysis *AA;

	// Valid Regions for Scop
	ScopDetection *SD;

	// Target data for element size computing.
	const DataLayout *TD;

	// Access function of statements (currently BasicBlocks) .
	AccFuncMapType AccFuncMap;

	// Pre-created zero for the scalar accesses, with it we do not need create a
	// zero scev every time when we need it.
	const SCEV *ZeroOffset;

	// The TempScop for this region.
	TempScop *TempScopOfRegion;

	// Clear the context.
	void clear();

	// Build the temprory information of Region R, where R must be a valid part
	// of Scop.
	TempScop *buildTempScop(Region &R);

	/// @brief Build an instance of IRAccess from the Load/Store instruction.
	///
	/// @param Inst The Load/Store instruction that access the memory
	/// @param L The parent loop of the instruction
	/// @param R The region on which we are going to build a TempScop
	/// @param BoxedLoops The set of loops that are overapproximated in @p R.
	///
	/// @return The IRAccess to describe the access function of the
	/// instruction.
	IRAccess buildIRAccess(Instruction Inst, Loop L, Region *R,
	const ScopDetection::BoxedLoopsSetTy *BoxedLoops);

	/// @brief Analyze and extract the cross-BB scalar dependences (or,
	/// dataflow dependencies) of an instruction.
	///
	/// @param Inst The instruction to be analyzed
	/// @param R The SCoP region
	/// @param NonAffineSubRegion The non affine sub-region @p Inst is in.
	///
	/// @return True if the Instruction is used in other BB and a scalar write
	/// Access is required.
	bool buildScalarDependences(Instruction Inst, Region R,
	Region *NonAffineSubRegio);

	/// @brief Create IRAccesses for the given PHI node in the given region.
	///
	/// @param PHI The PHI node to be handled
	/// @param R The SCoP region
	/// @param Functions The access functions of the current BB
	/// @param NonAffineSubRegion The non affine sub-region @p PHI is in.
	void buildPHIAccesses(PHINode *PHI, Region &R, AccFuncSetType &Functions,
	Region *NonAffineSubRegion);

	/// @brief Build the access functions for the subregion @p SR.
	///
	/// @param R The SCoP region.
	/// @param SR A subregion of @p R.
	void buildAccessFunctions(Region &R, Region &SR);

	/// @brief Build the access functions for the basic block @p BB
	///
	/// @param R The SCoP region.
	/// @param BB A basic block in @p R.
	/// @param NonAffineSubRegion The non affine sub-region @p BB is in.
	void buildAccessFunctions(Region &R, BasicBlock &BB,
	Region *NonAffineSubRegion = nullptr);

	public:
	static char ID;
	explicit TempScopInfo() : RegionPass(ID), TempScopOfRegion(nullptr) {}
	~TempScopInfo();

	/// @brief Get the temporay Scop information in LLVM IR for this region.
	///
	/// @return The Scop information in LLVM IR represent.
	TempScop *getTempScop() const;

	/// @name RegionPass interface
	//@{
	virtual void getAnalysisUsage(AnalysisUsage &AU) const;
	virtual void releaseMemory() { clear(); }
	virtual bool runOnRegion(Region *R, RGPassManager &RGM);
	virtual void print(raw_ostream &OS, const Module *) const;
	//@}
	};

	} // end namespace polly

	namespace llvm {
	class PassRegistry;
	void initializeTempScopInfoPass(llvm::PassRegistry &);
	}

	#endif

lib/Analysis/ScopInfo.cpp

Show All 17 Lines
//===----------------------------------------------------------------------===//		//===----------------------------------------------------------------------===//

#include "polly/LinkAllPasses.h"		#include "polly/LinkAllPasses.h"
#include "polly/Options.h"		#include "polly/Options.h"
#include "polly/ScopInfo.h"		#include "polly/ScopInfo.h"
#include "polly/Support/GICHelper.h"		#include "polly/Support/GICHelper.h"
#include "polly/Support/SCEVValidator.h"		#include "polly/Support/SCEVValidator.h"
#include "polly/Support/ScopHelper.h"		#include "polly/Support/ScopHelper.h"
#include "polly/TempScopInfo.h"		#include "polly/CodeGen/BlockGenerators.h"
#include "llvm/ADT/MapVector.h"		#include "llvm/ADT/MapVector.h"
#include "llvm/ADT/SetVector.h"		#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/Statistic.h"		#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/STLExtras.h"		#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/StringExtras.h"		#include "llvm/ADT/StringExtras.h"
#include "llvm/ADT/PostOrderIterator.h"		#include "llvm/ADT/PostOrderIterator.h"
#include "llvm/Analysis/AliasAnalysis.h"		#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/LoopInfo.h"		#include "llvm/Analysis/LoopInfo.h"
Show All 19 Lines
using namespace llvm;		using namespace llvm;
using namespace polly;		using namespace polly;

#define DEBUG_TYPE "polly-scops"		#define DEBUG_TYPE "polly-scops"

STATISTIC(ScopFound, "Number of valid Scops");		STATISTIC(ScopFound, "Number of valid Scops");
STATISTIC(RichScopFound, "Number of Scops containing a loop");		STATISTIC(RichScopFound, "Number of Scops containing a loop");

		static cl::opt<bool> ModelReadOnlyScalars(
		"polly-analyze-read-only-scalars",
		cl::desc("Model read-only scalar values in the scop description"),
		cl::Hidden, cl::ZeroOrMore, cl::init(true), cl::cat(PollyCategory));

// Multiplicative reductions can be disabled separately as these kind of		// Multiplicative reductions can be disabled separately as these kind of
// operations can overflow easily. Additive reductions and bit operations		// operations can overflow easily. Additive reductions and bit operations
// are in contrast pretty stable.		// are in contrast pretty stable.
static cl::opt<bool> DisableMultiplicativeReductions(		static cl::opt<bool> DisableMultiplicativeReductions(
"polly-disable-multiplicative-reductions",		"polly-disable-multiplicative-reductions",
cl::desc("Disable multiplicative reductions"), cl::Hidden, cl::ZeroOrMore,		cl::desc("Disable multiplicative reductions"), cl::Hidden, cl::ZeroOrMore,
cl::init(false), cl::cat(PollyCategory));		cl::init(false), cl::cat(PollyCategory));

Show All 11 Lines	static cl::opt<std::string> UserContextStr(
cl::desc("Provide additional constraints on the context parameters"),		cl::desc("Provide additional constraints on the context parameters"),
cl::init(""), cl::cat(PollyCategory));		cl::init(""), cl::cat(PollyCategory));

static cl::opt<bool> DetectReductions("polly-detect-reductions",		static cl::opt<bool> DetectReductions("polly-detect-reductions",
cl::desc("Detect and exploit reductions"),		cl::desc("Detect and exploit reductions"),
cl::Hidden, cl::ZeroOrMore,		cl::Hidden, cl::ZeroOrMore,
cl::init(true), cl::cat(PollyCategory));		cl::init(true), cl::cat(PollyCategory));

		//===----------------------------------------------------------------------===//
		/// Helper Classes

		void Comparison::print(raw_ostream &OS) const {
		// Not yet implemented.
		}

// Create a sequence of two schedules. Either argument may be null and is		// Create a sequence of two schedules. Either argument may be null and is
// interpreted as the empty schedule. Can also return null if both schedules are		// interpreted as the empty schedule. Can also return null if both schedules are
// empty.		// empty.
static __isl_give isl_schedule *		static __isl_give isl_schedule *
combineInSequence(__isl_take isl_schedule *Prev,		combineInSequence(__isl_take isl_schedule *Prev,
__isl_take isl_schedule *Succ) {		__isl_take isl_schedule *Succ) {
if (!Prev)		if (!Prev)
return Succ;		return Succ;
▲ Show 20 Lines • Show All 111 Lines • ▼ Show 20 Lines

const ScopArrayInfo ScopArrayInfo::getFromId(isl_id Id) {		const ScopArrayInfo ScopArrayInfo::getFromId(isl_id Id) {
void *User = isl_id_get_user(Id);		void *User = isl_id_get_user(Id);
const ScopArrayInfo SAI = static_cast<ScopArrayInfo >(User);		const ScopArrayInfo SAI = static_cast<ScopArrayInfo >(User);
isl_id_free(Id);		isl_id_free(Id);
return SAI;		return SAI;
}		}

		void IRAccess::print(raw_ostream &OS) const {
		if (isRead())
		OS << "Read ";
		else {
		if (isMayWrite())
		OS << "May";
		OS << "Write ";
		}
		OS << BaseAddress->getName() << '[' << *Offset << "]\n";
		}

const std::string		const std::string
MemoryAccess::getReductionOperatorStr(MemoryAccess::ReductionType RT) {		MemoryAccess::getReductionOperatorStr(MemoryAccess::ReductionType RT) {
switch (RT) {		switch (RT) {
case MemoryAccess::RT_NONE:		case MemoryAccess::RT_NONE:
llvm_unreachable("Requested a reduction operator string for a memory "		llvm_unreachable("Requested a reduction operator string for a memory "
"access which isn't a reduction");		"access which isn't a reduction");
case MemoryAccess::RT_ADD:		case MemoryAccess::RT_ADD:
return "+";		return "+";
▲ Show 20 Lines • Show All 2,098 Lines • ▼ Show 20 Lines

ScopStmt Scop::getStmtForBasicBlock(BasicBlock BB) const {		ScopStmt Scop::getStmtForBasicBlock(BasicBlock BB) const {
auto StmtMapIt = StmtMap.find(BB);		auto StmtMapIt = StmtMap.find(BB);
if (StmtMapIt == StmtMap.end())		if (StmtMapIt == StmtMap.end())
return nullptr;		return nullptr;
return StmtMapIt->second;		return StmtMapIt->second;
}		}

		//===----------------------------------------------------------------------===//
		// TempScop implementation
		TempScop::~TempScop() {}

		void TempScop::print(raw_ostream &OS, ScalarEvolution SE, LoopInfo LI) const {
		OS << "Scop: " << R.getNameStr() << "\n";

		printDetail(OS, SE, LI, &R, 0);
		}

		void TempScop::printDetail(raw_ostream &OS, ScalarEvolution SE, LoopInfo LI,
		const Region *CurR, unsigned ind) const {
		// FIXME: Print other details rather than memory accesses.
		for (const auto &CurBlock : CurR->blocks()) {
		AccFuncMapType::const_iterator AccSetIt = AccFuncMap.find(CurBlock);

		// Ignore trivial blocks that do not contain any memory access.
		if (AccSetIt == AccFuncMap.end())
		continue;

		OS.indent(ind) << "BB: " << CurBlock->getName() << '\n';
		typedef AccFuncSetType::const_iterator access_iterator;
		const AccFuncSetType &AccFuncs = AccSetIt->second;

		for (access_iterator AI = AccFuncs.begin(), AE = AccFuncs.end(); AI != AE;
		++AI)
		AI->first.print(OS.indent(ind + 2));
		}
		}

int Scop::getRelativeLoopDepth(const Loop *L) const {		int Scop::getRelativeLoopDepth(const Loop *L) const {
Loop *OuterLoop =		Loop *OuterLoop =
L ? R.outermostLoopInRegion(const_cast<Loop *>(L)) : nullptr;		L ? R.outermostLoopInRegion(const_cast<Loop *>(L)) : nullptr;
if (!OuterLoop)		if (!OuterLoop)
return -1;		return -1;
return L->getLoopDepth() - OuterLoop->getLoopDepth();		return L->getLoopDepth() - OuterLoop->getLoopDepth();
}		}

		void TempScopInfo::buildPHIAccesses(PHINode *PHI, Region &R,
		AccFuncSetType &Functions,
		Region *NonAffineSubRegion) {
		if (canSynthesize(PHI, LI, SE, &R))
		return;

		// PHI nodes are modeled as if they had been demoted prior to the SCoP
		// detection. Hence, the PHI is a load of a new memory location in which the
		// incoming value was written at the end of the incoming basic block.
		bool OnlyNonAffineSubRegionOperands = true;
		for (unsigned u = 0; u < PHI->getNumIncomingValues(); u++) {
		Value *Op = PHI->getIncomingValue(u);
		BasicBlock *OpBB = PHI->getIncomingBlock(u);

		// Do not build scalar dependences inside a non-affine subregion.
		if (NonAffineSubRegion && NonAffineSubRegion->contains(OpBB))
		continue;

		OnlyNonAffineSubRegionOperands = false;

		if (!R.contains(OpBB))
		continue;

		Instruction *OpI = dyn_cast<Instruction>(Op);
		if (OpI) {
		BasicBlock *OpIBB = OpI->getParent();
		// As we pretend there is a use (or more precise a write) of OpI in OpBB
		// we have to insert a scalar dependence from the definition of OpI to
		// OpBB if the definition is not in OpBB.
		if (OpIBB != OpBB) {
		IRAccess ScalarRead(IRAccess::READ, OpI, ZeroOffset, 1, true, OpI);
		AccFuncMap[OpBB].push_back(std::make_pair(ScalarRead, PHI));
		IRAccess ScalarWrite(IRAccess::MUST_WRITE, OpI, ZeroOffset, 1, true,
		OpI);
		AccFuncMap[OpIBB].push_back(std::make_pair(ScalarWrite, OpI));
		}
		}

		// Always use the terminator of the incoming basic block as the access
		// instruction.
		OpI = OpBB->getTerminator();

		IRAccess ScalarAccess(IRAccess::MUST_WRITE, PHI, ZeroOffset, 1, true, Op,
		/* IsPHI */ true);
		AccFuncMap[OpBB].push_back(std::make_pair(ScalarAccess, OpI));
		}

		if (!OnlyNonAffineSubRegionOperands) {
		IRAccess ScalarAccess(IRAccess::READ, PHI, ZeroOffset, 1, true, PHI,
		/* IsPHI */ true);
		Functions.push_back(std::make_pair(ScalarAccess, PHI));
		}
		}

		bool TempScopInfo::buildScalarDependences(Instruction Inst, Region R,
		Region *NonAffineSubRegion) {
		bool canSynthesizeInst = canSynthesize(Inst, LI, SE, R);
		if (isIgnoredIntrinsic(Inst))
		return false;

		bool AnyCrossStmtUse = false;
		BasicBlock *ParentBB = Inst->getParent();

		for (User *U : Inst->users()) {
		Instruction *UI = dyn_cast<Instruction>(U);

		// Ignore the strange user
		if (UI == 0)
		continue;

		BasicBlock *UseParent = UI->getParent();

		// Ignore the users in the same BB (statement)
		if (UseParent == ParentBB)
		continue;

		// Do not build scalar dependences inside a non-affine subregion.
		if (NonAffineSubRegion && NonAffineSubRegion->contains(UseParent))
		continue;

		// Check whether or not the use is in the SCoP.
		if (!R->contains(UseParent)) {
		AnyCrossStmtUse = true;
		continue;
		}

		// If the instruction can be synthesized and the user is in the region
		// we do not need to add scalar dependences.
		if (canSynthesizeInst)
		continue;

		// No need to translate these scalar dependences into polyhedral form,
		// because synthesizable scalars can be generated by the code generator.
		if (canSynthesize(UI, LI, SE, R))
		continue;

		// Skip PHI nodes in the region as they handle their operands on their own.
		if (isa<PHINode>(UI))
		continue;

		// Now U is used in another statement.
		AnyCrossStmtUse = true;

		// Do not build a read access that is not in the current SCoP
		// Use the def instruction as base address of the IRAccess, so that it will
		// become the name of the scalar access in the polyhedral form.
		IRAccess ScalarAccess(IRAccess::READ, Inst, ZeroOffset, 1, true, Inst);
		AccFuncMap[UseParent].push_back(std::make_pair(ScalarAccess, UI));
		}

		if (ModelReadOnlyScalars) {
		for (Value *Op : Inst->operands()) {
		if (canSynthesize(Op, LI, SE, R))
		continue;

		if (Instruction *OpInst = dyn_cast<Instruction>(Op))
		if (R->contains(OpInst))
		continue;

		if (isa<Constant>(Op))
		continue;

		IRAccess ScalarAccess(IRAccess::READ, Op, ZeroOffset, 1, true, Op);
		AccFuncMap[Inst->getParent()].push_back(
		std::make_pair(ScalarAccess, Inst));
		}
		}

		return AnyCrossStmtUse;
		}

		extern MapInsnToMemAcc InsnToMemAcc;

		IRAccess
		TempScopInfo::buildIRAccess(Instruction Inst, Loop L, Region *R,
		const ScopDetection::BoxedLoopsSetTy *BoxedLoops) {
		unsigned Size;
		Type *SizeType;
		Value *Val;
		enum IRAccess::TypeKind Type;

		if (LoadInst *Load = dyn_cast<LoadInst>(Inst)) {
		SizeType = Load->getType();
		Size = TD->getTypeStoreSize(SizeType);
		Type = IRAccess::READ;
		Val = Load;
		} else {
		StoreInst *Store = cast<StoreInst>(Inst);
		SizeType = Store->getValueOperand()->getType();
		Size = TD->getTypeStoreSize(SizeType);
		Type = IRAccess::MUST_WRITE;
		Val = Store->getValueOperand();
		}

		const SCEV AccessFunction = SE->getSCEVAtScope(getPointerOperand(Inst), L);
		const SCEVUnknown *BasePointer =
		dyn_cast<SCEVUnknown>(SE->getPointerBase(AccessFunction));

		assert(BasePointer && "Could not find base pointer");
		AccessFunction = SE->getMinusSCEV(AccessFunction, BasePointer);

		auto AccItr = InsnToMemAcc.find(Inst);
		if (PollyDelinearize && AccItr != InsnToMemAcc.end())
		return IRAccess(Type, BasePointer->getValue(), AccessFunction, Size, true,
		AccItr->second.DelinearizedSubscripts,
		AccItr->second.Shape->DelinearizedSizes, Val);

		// Check if the access depends on a loop contained in a non-affine subregion.
		bool isVariantInNonAffineLoop = false;
		if (BoxedLoops) {
		SetVector<const Loop *> Loops;
		findLoops(AccessFunction, Loops);
		for (const Loop *L : Loops)
		if (BoxedLoops->count(L))
		isVariantInNonAffineLoop = true;
		}

		bool IsAffine = !isVariantInNonAffineLoop &&
		isAffineExpr(R, AccessFunction, *SE, BasePointer->getValue());

		SmallVector<const SCEV *, 4> Subscripts, Sizes;
		Subscripts.push_back(AccessFunction);
		Sizes.push_back(SE->getConstant(ZeroOffset->getType(), Size));

		if (!IsAffine && Type == IRAccess::MUST_WRITE)
		Type = IRAccess::MAY_WRITE;

		return IRAccess(Type, BasePointer->getValue(), AccessFunction, Size, IsAffine,
		Subscripts, Sizes, Val);
		}

		void TempScopInfo::buildAccessFunctions(Region &R, Region &SR) {

		if (SD->isNonAffineSubRegion(&SR, &R)) {
		for (BasicBlock *BB : SR.blocks())
		buildAccessFunctions(R, *BB, &SR);
		return;
		}

		for (auto I = SR.element_begin(), E = SR.element_end(); I != E; ++I)
		if (I->isSubRegion())
		buildAccessFunctions(R, *I->getNodeAs<Region>());
		else
		buildAccessFunctions(R, *I->getNodeAs<BasicBlock>());
		}

		void TempScopInfo::buildAccessFunctions(Region &R, BasicBlock &BB,
		Region *NonAffineSubRegion) {
		AccFuncSetType Functions;
		Loop *L = LI->getLoopFor(&BB);

		// The set of loops contained in non-affine subregions that are part of R.
		const ScopDetection::BoxedLoopsSetTy *BoxedLoops = SD->getBoxedLoops(&R);

		for (BasicBlock::iterator I = BB.begin(), E = --BB.end(); I != E; ++I) {
		Instruction *Inst = I;
		if (isa<LoadInst>(Inst) \|\| isa<StoreInst>(Inst))
		Functions.push_back(
		std::make_pair(buildIRAccess(Inst, L, &R, BoxedLoops), Inst));

		if (isIgnoredIntrinsic(Inst))
		continue;

		if (PHINode *PHI = dyn_cast<PHINode>(Inst))
		buildPHIAccesses(PHI, R, Functions, NonAffineSubRegion);

		if (buildScalarDependences(Inst, &R, NonAffineSubRegion)) {
		// If the Instruction is used outside the statement, we need to build the
		// write access.
		if (!isa<StoreInst>(Inst)) {
		IRAccess ScalarAccess(IRAccess::MUST_WRITE, Inst, ZeroOffset, 1, true,
		Inst);
		Functions.push_back(std::make_pair(ScalarAccess, Inst));
		}
		}
		}

		if (Functions.empty())
		return;

		AccFuncSetType &Accs = AccFuncMap[&BB];
		Accs.insert(Accs.end(), Functions.begin(), Functions.end());
		}

		TempScop *TempScopInfo::buildTempScop(Region &R) {
		TempScop *TScop = new TempScop(R, AccFuncMap);

		buildAccessFunctions(R, R);

		return TScop;
		}

		TempScop *TempScopInfo::getTempScop() const { return TempScopOfRegion; }

		void TempScopInfo::print(raw_ostream &OS, const Module *) const {
		if (TempScopOfRegion)
		TempScopOfRegion->print(OS, SE, LI);
		}

		bool TempScopInfo::runOnRegion(Region *R, RGPassManager &RGM) {
		SD = &getAnalysis<ScopDetection>();

		if (!SD->isMaxRegionInScop(*R))
		return false;

		Function *F = R->getEntry()->getParent();
		SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
		LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
		AA = &getAnalysis<AliasAnalysis>();
		TD = &F->getParent()->getDataLayout();
		ZeroOffset = SE->getConstant(TD->getIntPtrType(F->getContext()), 0);

		assert(!TempScopOfRegion && "Build the TempScop only once");
		TempScopOfRegion = buildTempScop(*R);

		return false;
		}

		void TempScopInfo::getAnalysisUsage(AnalysisUsage &AU) const {
		AU.addRequiredTransitive<LoopInfoWrapperPass>();
		AU.addRequiredTransitive<ScalarEvolutionWrapperPass>();
		AU.addRequiredTransitive<ScopDetection>();
		AU.addRequiredID(IndependentBlocksID);
		AU.addRequired<AliasAnalysis>();
		AU.setPreservesAll();
		}

		TempScopInfo::~TempScopInfo() { clear(); }

		void TempScopInfo::clear() {
		AccFuncMap.clear();
		if (TempScopOfRegion)
		delete TempScopOfRegion;
		TempScopOfRegion = nullptr;
		}

		//===----------------------------------------------------------------------===//
		// TempScop information extraction pass implement
		char TempScopInfo::ID = 0;

		Pass *polly::createTempScopInfoPass() { return new TempScopInfo(); }

		INITIALIZE_PASS_BEGIN(TempScopInfo, "polly-analyze-ir",
		"Polly - Analyse the LLVM-IR in the detected regions",
		false, false);
		INITIALIZE_AG_DEPENDENCY(AliasAnalysis);
		INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass);
		INITIALIZE_PASS_DEPENDENCY(RegionInfoPass);
		INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass);
		INITIALIZE_PASS_END(TempScopInfo, "polly-analyze-ir",
		"Polly - Analyse the LLVM-IR in the detected regions",
		false, false)

//===----------------------------------------------------------------------===//		//===----------------------------------------------------------------------===//
ScopInfo::ScopInfo() : RegionPass(ID), scop(0) {		ScopInfo::ScopInfo() : RegionPass(ID), scop(0) {
ctx = isl_ctx_alloc();		ctx = isl_ctx_alloc();
isl_options_set_on_error(ctx, ISL_ON_ERROR_ABORT);		isl_options_set_on_error(ctx, ISL_ON_ERROR_ABORT);
}		}

ScopInfo::~ScopInfo() {		ScopInfo::~ScopInfo() {
clear();		clear();
▲ Show 20 Lines • Show All 63 Lines • Show Last 20 Lines

lib/Analysis/TempScopInfo.cpp

This file was deleted.

	//===---------- TempScopInfo.cpp - Extract TempScops ---------------------===//
	//
	// The LLVM Compiler Infrastructure
	//
	// This file is distributed under the University of Illinois Open Source
	// License. See LICENSE.TXT for details.
	//
	//===----------------------------------------------------------------------===//
	//
	// Collect information about the control flow regions detected by the Scop
	// detection, such that this information can be translated info its polyhedral
	// representation.
	//
	//===----------------------------------------------------------------------===//

	#include "polly/TempScopInfo.h"
	#include "polly/Options.h"
	#include "polly/CodeGen/BlockGenerators.h"
	#include "polly/LinkAllPasses.h"
	#include "polly/ScopDetection.h"
	#include "polly/Support/GICHelper.h"
	#include "polly/Support/SCEVValidator.h"
	#include "polly/Support/ScopHelper.h"
	#include "llvm/ADT/STLExtras.h"
	#include "llvm/Analysis/AliasAnalysis.h"
	#include "llvm/Analysis/LoopInfo.h"
	#include "llvm/Analysis/PostDominators.h"
	#include "llvm/Analysis/RegionIterator.h"
	#include "llvm/Analysis/ScalarEvolution.h"
	#include "llvm/Analysis/ScalarEvolutionExpressions.h"
	#include "llvm/IR/DataLayout.h"
	#include "llvm/IR/Module.h"
	#include "llvm/Support/Debug.h"

	using namespace llvm;
	using namespace polly;

	static cl::opt<bool> ModelReadOnlyScalars(
	"polly-analyze-read-only-scalars",
	cl::desc("Model read-only scalar values in the scop description"),
	cl::Hidden, cl::ZeroOrMore, cl::init(true), cl::cat(PollyCategory));

	#define DEBUG_TYPE "polly-analyze-ir"

	//===----------------------------------------------------------------------===//
	/// Helper Classes

	void IRAccess::print(raw_ostream &OS) const {
	if (isRead())
	OS << "Read ";
	else {
	if (isMayWrite())
	OS << "May";
	OS << "Write ";
	}
	OS << BaseAddress->getName() << '[' << *Offset << "]\n";
	}

	void Comparison::print(raw_ostream &OS) const {
	// Not yet implemented.
	}

	//===----------------------------------------------------------------------===//
	// TempScop implementation
	TempScop::~TempScop() {}

	void TempScop::print(raw_ostream &OS, ScalarEvolution SE, LoopInfo LI) const {
	OS << "Scop: " << R.getNameStr() << "\n";

	printDetail(OS, SE, LI, &R, 0);
	}

	void TempScop::printDetail(raw_ostream &OS, ScalarEvolution SE, LoopInfo LI,
	const Region *CurR, unsigned ind) const {
	// FIXME: Print other details rather than memory accesses.
	for (const auto &CurBlock : CurR->blocks()) {
	AccFuncMapType::const_iterator AccSetIt = AccFuncMap.find(CurBlock);

	// Ignore trivial blocks that do not contain any memory access.
	if (AccSetIt == AccFuncMap.end())
	continue;

	OS.indent(ind) << "BB: " << CurBlock->getName() << '\n';
	typedef AccFuncSetType::const_iterator access_iterator;
	const AccFuncSetType &AccFuncs = AccSetIt->second;

	for (access_iterator AI = AccFuncs.begin(), AE = AccFuncs.end(); AI != AE;
	++AI)
	AI->first.print(OS.indent(ind + 2));
	}
	}

	void TempScopInfo::buildPHIAccesses(PHINode *PHI, Region &R,
	AccFuncSetType &Functions,
	Region *NonAffineSubRegion) {
	if (canSynthesize(PHI, LI, SE, &R))
	return;

	// PHI nodes are modeled as if they had been demoted prior to the SCoP
	// detection. Hence, the PHI is a load of a new memory location in which the
	// incoming value was written at the end of the incoming basic block.
	bool OnlyNonAffineSubRegionOperands = true;
	for (unsigned u = 0; u < PHI->getNumIncomingValues(); u++) {
	Value *Op = PHI->getIncomingValue(u);
	BasicBlock *OpBB = PHI->getIncomingBlock(u);

	// Do not build scalar dependences inside a non-affine subregion.
	if (NonAffineSubRegion && NonAffineSubRegion->contains(OpBB))
	continue;

	OnlyNonAffineSubRegionOperands = false;

	if (!R.contains(OpBB))
	continue;

	Instruction *OpI = dyn_cast<Instruction>(Op);
	if (OpI) {
	BasicBlock *OpIBB = OpI->getParent();
	// As we pretend there is a use (or more precise a write) of OpI in OpBB
	// we have to insert a scalar dependence from the definition of OpI to
	// OpBB if the definition is not in OpBB.
	if (OpIBB != OpBB) {
	IRAccess ScalarRead(IRAccess::READ, OpI, ZeroOffset, 1, true, OpI);
	AccFuncMap[OpBB].push_back(std::make_pair(ScalarRead, PHI));
	IRAccess ScalarWrite(IRAccess::MUST_WRITE, OpI, ZeroOffset, 1, true,
	OpI);
	AccFuncMap[OpIBB].push_back(std::make_pair(ScalarWrite, OpI));
	}
	}

	// Always use the terminator of the incoming basic block as the access
	// instruction.
	OpI = OpBB->getTerminator();

	IRAccess ScalarAccess(IRAccess::MUST_WRITE, PHI, ZeroOffset, 1, true, Op,
	/* IsPHI */ true);
	AccFuncMap[OpBB].push_back(std::make_pair(ScalarAccess, OpI));
	}

	if (!OnlyNonAffineSubRegionOperands) {
	IRAccess ScalarAccess(IRAccess::READ, PHI, ZeroOffset, 1, true, PHI,
	/* IsPHI */ true);
	Functions.push_back(std::make_pair(ScalarAccess, PHI));
	}
	}

	bool TempScopInfo::buildScalarDependences(Instruction Inst, Region R,
	Region *NonAffineSubRegion) {
	bool canSynthesizeInst = canSynthesize(Inst, LI, SE, R);
	if (isIgnoredIntrinsic(Inst))
	return false;

	bool AnyCrossStmtUse = false;
	BasicBlock *ParentBB = Inst->getParent();

	for (User *U : Inst->users()) {
	Instruction *UI = dyn_cast<Instruction>(U);

	// Ignore the strange user
	if (UI == 0)
	continue;

	BasicBlock *UseParent = UI->getParent();

	// Ignore the users in the same BB (statement)
	if (UseParent == ParentBB)
	continue;

	// Do not build scalar dependences inside a non-affine subregion.
	if (NonAffineSubRegion && NonAffineSubRegion->contains(UseParent))
	continue;

	// Check whether or not the use is in the SCoP.
	if (!R->contains(UseParent)) {
	AnyCrossStmtUse = true;
	continue;
	}

	// If the instruction can be synthesized and the user is in the region
	// we do not need to add scalar dependences.
	if (canSynthesizeInst)
	continue;

	// No need to translate these scalar dependences into polyhedral form,
	// because synthesizable scalars can be generated by the code generator.
	if (canSynthesize(UI, LI, SE, R))
	continue;

	// Skip PHI nodes in the region as they handle their operands on their own.
	if (isa<PHINode>(UI))
	continue;

	// Now U is used in another statement.
	AnyCrossStmtUse = true;

	// Do not build a read access that is not in the current SCoP
	// Use the def instruction as base address of the IRAccess, so that it will
	// become the name of the scalar access in the polyhedral form.
	IRAccess ScalarAccess(IRAccess::READ, Inst, ZeroOffset, 1, true, Inst);
	AccFuncMap[UseParent].push_back(std::make_pair(ScalarAccess, UI));
	}

	if (ModelReadOnlyScalars) {
	for (Value *Op : Inst->operands()) {
	if (canSynthesize(Op, LI, SE, R))
	continue;

	if (Instruction *OpInst = dyn_cast<Instruction>(Op))
	if (R->contains(OpInst))
	continue;

	if (isa<Constant>(Op))
	continue;

	IRAccess ScalarAccess(IRAccess::READ, Op, ZeroOffset, 1, true, Op);
	AccFuncMap[Inst->getParent()].push_back(
	std::make_pair(ScalarAccess, Inst));
	}
	}

	return AnyCrossStmtUse;
	}

	extern MapInsnToMemAcc InsnToMemAcc;

	IRAccess
	TempScopInfo::buildIRAccess(Instruction Inst, Loop L, Region *R,
	const ScopDetection::BoxedLoopsSetTy *BoxedLoops) {
	unsigned Size;
	Type *SizeType;
	Value *Val;
	enum IRAccess::TypeKind Type;

	if (LoadInst *Load = dyn_cast<LoadInst>(Inst)) {
	SizeType = Load->getType();
	Size = TD->getTypeStoreSize(SizeType);
	Type = IRAccess::READ;
	Val = Load;
	} else {
	StoreInst *Store = cast<StoreInst>(Inst);
	SizeType = Store->getValueOperand()->getType();
	Size = TD->getTypeStoreSize(SizeType);
	Type = IRAccess::MUST_WRITE;
	Val = Store->getValueOperand();
	}

	const SCEV AccessFunction = SE->getSCEVAtScope(getPointerOperand(Inst), L);
	const SCEVUnknown *BasePointer =
	dyn_cast<SCEVUnknown>(SE->getPointerBase(AccessFunction));

	assert(BasePointer && "Could not find base pointer");
	AccessFunction = SE->getMinusSCEV(AccessFunction, BasePointer);

	auto AccItr = InsnToMemAcc.find(Inst);
	if (PollyDelinearize && AccItr != InsnToMemAcc.end())
	return IRAccess(Type, BasePointer->getValue(), AccessFunction, Size, true,
	AccItr->second.DelinearizedSubscripts,
	AccItr->second.Shape->DelinearizedSizes, Val);

	// Check if the access depends on a loop contained in a non-affine subregion.
	bool isVariantInNonAffineLoop = false;
	if (BoxedLoops) {
	SetVector<const Loop *> Loops;
	findLoops(AccessFunction, Loops);
	for (const Loop *L : Loops)
	if (BoxedLoops->count(L))
	isVariantInNonAffineLoop = true;
	}

	bool IsAffine = !isVariantInNonAffineLoop &&
	isAffineExpr(R, AccessFunction, *SE, BasePointer->getValue());

	SmallVector<const SCEV *, 4> Subscripts, Sizes;
	Subscripts.push_back(AccessFunction);
	Sizes.push_back(SE->getConstant(ZeroOffset->getType(), Size));

	if (!IsAffine && Type == IRAccess::MUST_WRITE)
	Type = IRAccess::MAY_WRITE;

	return IRAccess(Type, BasePointer->getValue(), AccessFunction, Size, IsAffine,
	Subscripts, Sizes, Val);
	}

	void TempScopInfo::buildAccessFunctions(Region &R, Region &SR) {

	if (SD->isNonAffineSubRegion(&SR, &R)) {
	for (BasicBlock *BB : SR.blocks())
	buildAccessFunctions(R, *BB, &SR);
	return;
	}

	for (auto I = SR.element_begin(), E = SR.element_end(); I != E; ++I)
	if (I->isSubRegion())
	buildAccessFunctions(R, *I->getNodeAs<Region>());
	else
	buildAccessFunctions(R, *I->getNodeAs<BasicBlock>());
	}

	void TempScopInfo::buildAccessFunctions(Region &R, BasicBlock &BB,
	Region *NonAffineSubRegion) {
	AccFuncSetType Functions;
	Loop *L = LI->getLoopFor(&BB);

	// The set of loops contained in non-affine subregions that are part of R.
	const ScopDetection::BoxedLoopsSetTy *BoxedLoops = SD->getBoxedLoops(&R);

	for (BasicBlock::iterator I = BB.begin(), E = --BB.end(); I != E; ++I) {
	Instruction *Inst = I;
	if (isa<LoadInst>(Inst) \|\| isa<StoreInst>(Inst))
	Functions.push_back(
	std::make_pair(buildIRAccess(Inst, L, &R, BoxedLoops), Inst));

	if (isIgnoredIntrinsic(Inst))
	continue;

	if (PHINode *PHI = dyn_cast<PHINode>(Inst))
	buildPHIAccesses(PHI, R, Functions, NonAffineSubRegion);

	if (buildScalarDependences(Inst, &R, NonAffineSubRegion)) {
	// If the Instruction is used outside the statement, we need to build the
	// write access.
	if (!isa<StoreInst>(Inst)) {
	IRAccess ScalarAccess(IRAccess::MUST_WRITE, Inst, ZeroOffset, 1, true,
	Inst);
	Functions.push_back(std::make_pair(ScalarAccess, Inst));
	}
	}
	}

	if (Functions.empty())
	return;

	AccFuncSetType &Accs = AccFuncMap[&BB];
	Accs.insert(Accs.end(), Functions.begin(), Functions.end());
	}

	TempScop *TempScopInfo::buildTempScop(Region &R) {
	TempScop *TScop = new TempScop(R, AccFuncMap);

	buildAccessFunctions(R, R);

	return TScop;
	}

	TempScop *TempScopInfo::getTempScop() const { return TempScopOfRegion; }

	void TempScopInfo::print(raw_ostream &OS, const Module *) const {
	if (TempScopOfRegion)
	TempScopOfRegion->print(OS, SE, LI);
	}

	bool TempScopInfo::runOnRegion(Region *R, RGPassManager &RGM) {
	SD = &getAnalysis<ScopDetection>();

	if (!SD->isMaxRegionInScop(*R))
	return false;

	Function *F = R->getEntry()->getParent();
	SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
	LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
	AA = &getAnalysis<AliasAnalysis>();
	TD = &F->getParent()->getDataLayout();
	ZeroOffset = SE->getConstant(TD->getIntPtrType(F->getContext()), 0);

	assert(!TempScopOfRegion && "Build the TempScop only once");
	TempScopOfRegion = buildTempScop(*R);

	return false;
	}

	void TempScopInfo::getAnalysisUsage(AnalysisUsage &AU) const {
	AU.addRequiredTransitive<LoopInfoWrapperPass>();
	AU.addRequiredTransitive<ScalarEvolutionWrapperPass>();
	AU.addRequiredTransitive<ScopDetection>();
	AU.addRequiredID(IndependentBlocksID);
	AU.addRequired<AliasAnalysis>();
	AU.setPreservesAll();
	}

	TempScopInfo::~TempScopInfo() { clear(); }

	void TempScopInfo::clear() {
	AccFuncMap.clear();
	if (TempScopOfRegion)
	delete TempScopOfRegion;
	TempScopOfRegion = nullptr;
	}

	//===----------------------------------------------------------------------===//
	// TempScop information extraction pass implement
	char TempScopInfo::ID = 0;

	Pass *polly::createTempScopInfoPass() { return new TempScopInfo(); }

	INITIALIZE_PASS_BEGIN(TempScopInfo, "polly-analyze-ir",
	"Polly - Analyse the LLVM-IR in the detected regions",
	false, false);
	INITIALIZE_AG_DEPENDENCY(AliasAnalysis);
	INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass);
	INITIALIZE_PASS_DEPENDENCY(RegionInfoPass);
	INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass);
	INITIALIZE_PASS_END(TempScopInfo, "polly-analyze-ir",
	"Polly - Analyse the LLVM-IR in the detected regions",
	false, false)

lib/CMakeLists.txt

	Show First 20 Lines • Show All 269 Lines • ▼ Show 20 Lines

	add_polly_library(Polly			add_polly_library(Polly
	Analysis/DependenceInfo.cpp			Analysis/DependenceInfo.cpp
	Analysis/ScopDetection.cpp			Analysis/ScopDetection.cpp
	Analysis/ScopDetectionDiagnostic.cpp			Analysis/ScopDetectionDiagnostic.cpp
	Analysis/ScopInfo.cpp			Analysis/ScopInfo.cpp
	Analysis/ScopGraphPrinter.cpp			Analysis/ScopGraphPrinter.cpp
	Analysis/ScopPass.cpp			Analysis/ScopPass.cpp
	Analysis/TempScopInfo.cpp
	CodeGen/BlockGenerators.cpp			CodeGen/BlockGenerators.cpp
	${ISL_CODEGEN_FILES}			${ISL_CODEGEN_FILES}
	CodeGen/LoopGenerators.cpp			CodeGen/LoopGenerators.cpp
	CodeGen/IRBuilder.cpp			CodeGen/IRBuilder.cpp
	CodeGen/Utils.cpp			CodeGen/Utils.cpp
	CodeGen/RuntimeDebugBuilder.cpp			CodeGen/RuntimeDebugBuilder.cpp
	${GPGPU_CODEGEN_FILES}			${GPGPU_CODEGEN_FILES}
	Exchange/JSONExporter.cpp			Exchange/JSONExporter.cpp
	▲ Show 20 Lines • Show All 58 Lines • Show Last 20 Lines

lib/CodeGen/CodeGeneration.cpp

	Show All 20 Lines

	#include "polly/CodeGen/IslNodeBuilder.h"			#include "polly/CodeGen/IslNodeBuilder.h"
	#include "polly/CodeGen/IslAst.h"			#include "polly/CodeGen/IslAst.h"
	#include "polly/CodeGen/Utils.h"			#include "polly/CodeGen/Utils.h"
	#include "polly/DependenceInfo.h"			#include "polly/DependenceInfo.h"
	#include "polly/LinkAllPasses.h"			#include "polly/LinkAllPasses.h"
	#include "polly/ScopInfo.h"			#include "polly/ScopInfo.h"
	#include "polly/Support/ScopHelper.h"			#include "polly/Support/ScopHelper.h"
	#include "polly/TempScopInfo.h"
	#include "llvm/IR/Module.h"			#include "llvm/IR/Module.h"
	#include "llvm/IR/Verifier.h"			#include "llvm/IR/Verifier.h"
	#include "llvm/Support/Debug.h"			#include "llvm/Support/Debug.h"
	#include "llvm/Analysis/PostDominators.h"			#include "llvm/Analysis/PostDominators.h"

	using namespace polly;			using namespace polly;
	using namespace llvm;			using namespace llvm;

	▲ Show 20 Lines • Show All 165 Lines • Show Last 20 Lines

lib/CodeGen/IslNodeBuilder.cpp

	Show All 20 Lines
	#include "polly/CodeGen/Utils.h"			#include "polly/CodeGen/Utils.h"
	#include "polly/Config/config.h"			#include "polly/Config/config.h"
	#include "polly/DependenceInfo.h"			#include "polly/DependenceInfo.h"
	#include "polly/LinkAllPasses.h"			#include "polly/LinkAllPasses.h"
	#include "polly/ScopInfo.h"			#include "polly/ScopInfo.h"
	#include "polly/Support/GICHelper.h"			#include "polly/Support/GICHelper.h"
	#include "polly/Support/SCEVValidator.h"			#include "polly/Support/SCEVValidator.h"
	#include "polly/Support/ScopHelper.h"			#include "polly/Support/ScopHelper.h"
	#include "polly/TempScopInfo.h"
	#include "llvm/ADT/PostOrderIterator.h"			#include "llvm/ADT/PostOrderIterator.h"
	#include "llvm/ADT/SmallPtrSet.h"			#include "llvm/ADT/SmallPtrSet.h"
	#include "llvm/Analysis/LoopInfo.h"			#include "llvm/Analysis/LoopInfo.h"
	#include "llvm/Analysis/PostDominators.h"			#include "llvm/Analysis/PostDominators.h"
	#include "llvm/IR/DataLayout.h"			#include "llvm/IR/DataLayout.h"
	#include "llvm/IR/Module.h"			#include "llvm/IR/Module.h"
	#include "llvm/IR/Verifier.h"			#include "llvm/IR/Verifier.h"
	#include "llvm/Support/CommandLine.h"			#include "llvm/Support/CommandLine.h"
	▲ Show 20 Lines • Show All 807 Lines • Show Last 20 Lines

lib/Support/RegisterPasses.cpp

	Show All 21 Lines
	#include "polly/RegisterPasses.h"			#include "polly/RegisterPasses.h"
	#include "polly/Canonicalization.h"			#include "polly/Canonicalization.h"
	#include "polly/CodeGen/CodeGeneration.h"			#include "polly/CodeGen/CodeGeneration.h"
	#include "polly/DependenceInfo.h"			#include "polly/DependenceInfo.h"
	#include "polly/LinkAllPasses.h"			#include "polly/LinkAllPasses.h"
	#include "polly/Options.h"			#include "polly/Options.h"
	#include "polly/ScopDetection.h"			#include "polly/ScopDetection.h"
	#include "polly/ScopInfo.h"			#include "polly/ScopInfo.h"
	#include "polly/TempScopInfo.h"
	#include "llvm/Analysis/CFGPrinter.h"			#include "llvm/Analysis/CFGPrinter.h"
	#include "llvm/IR/LegacyPassManager.h"			#include "llvm/IR/LegacyPassManager.h"
	#include "llvm/Transforms/IPO/PassManagerBuilder.h"			#include "llvm/Transforms/IPO/PassManagerBuilder.h"
	#include "llvm/Transforms/Scalar.h"			#include "llvm/Transforms/Scalar.h"
	#include "llvm/Transforms/Vectorize.h"			#include "llvm/Transforms/Vectorize.h"

	using namespace llvm;			using namespace llvm;
	using namespace polly;			using namespace polly;
	▲ Show 20 Lines • Show All 296 Lines • Show Last 20 Lines

This is an archive of the discontinued LLVM Phabricator instance.

Merge TempScopInfo.{cpp|h} into ScopInfo.{cpp|h}ClosedPublic

Details

Diff Detail

Event Timeline

Revision Contents

Diff 34214

include/polly/ScopInfo.h

include/polly/TempScopInfo.h

lib/Analysis/ScopInfo.cpp

lib/Analysis/TempScopInfo.cpp

lib/CMakeLists.txt

lib/CodeGen/CodeGeneration.cpp

lib/CodeGen/IslNodeBuilder.cpp

lib/Support/RegisterPasses.cpp

Merge TempScopInfo.{cpp|h} into ScopInfo.{cpp|h}
ClosedPublic