Update prebuilt Clang to r416183b from Android.
https://android.googlesource.com/platform/prebuilts/clang/host/
linux-x86/+/06a71ddac05c22edb2d10b590e1769b3f8619bef
clang 12.0.5 (based on r416183b) from build 7284624.
Change-Id: I277a316abcf47307562d8b748b84870f31a72866
Signed-off-by: Olivier Deprez <olivier.deprez@arm.com>
diff --git a/linux-x64/clang/include/polly/Support/DumpModulePass.h b/linux-x64/clang/include/polly/Support/DumpModulePass.h
new file mode 100644
index 0000000..8299cfd
--- /dev/null
+++ b/linux-x64/clang/include/polly/Support/DumpModulePass.h
@@ -0,0 +1,39 @@
+//===------ DumpModulePass.h ------------------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// Write a module to a file.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef POLLY_SUPPORT_DUMPMODULEPASS_H
+#define POLLY_SUPPORT_DUMPMODULEPASS_H
+
+namespace llvm {
+class StringRef;
+class ModulePass;
+} // namespace llvm
+
+namespace polly {
+/// Create a pass that prints the module into a file.
+///
+/// The meaning of @p Filename depends on @p IsSuffix. If IsSuffix==false, then
+/// the module is written to the @p Filename. If it is true, the filename is
+/// generated from the module's name, @p Filename with an '.ll' extension.
+///
+/// The intent of IsSuffix is to avoid the file being overwritten when
+/// processing multiple modules and/or with multiple dump passes in the
+/// pipeline.
+llvm::ModulePass *createDumpModulePass(llvm::StringRef Filename, bool IsSuffix);
+} // namespace polly
+
+namespace llvm {
+class PassRegistry;
+void initializeDumpModulePass(llvm::PassRegistry &);
+} // namespace llvm
+
+#endif /* POLLY_SUPPORT_DUMPMODULEPASS_H */
diff --git a/linux-x64/clang/include/polly/Support/GICHelper.h b/linux-x64/clang/include/polly/Support/GICHelper.h
new file mode 100644
index 0000000..ca8abe4
--- /dev/null
+++ b/linux-x64/clang/include/polly/Support/GICHelper.h
@@ -0,0 +1,415 @@
+//===- Support/GICHelper.h -- Helper functions for ISL --------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// Helper functions for isl objects.
+//
+//===----------------------------------------------------------------------===//
+//
+#ifndef POLLY_SUPPORT_GIC_HELPER_H
+#define POLLY_SUPPORT_GIC_HELPER_H
+
+#include "llvm/ADT/APInt.h"
+#include "llvm/IR/DiagnosticInfo.h"
+#include "llvm/Support/raw_ostream.h"
+#include "isl/ctx.h"
+#include "isl/isl-noexceptions.h"
+#include "isl/options.h"
+
+namespace polly {
+
+/// Translate an llvm::APInt to an isl_val.
+///
+/// Translate the bitsequence without sign information as provided by APInt into
+/// a signed isl_val type. Depending on the value of @p IsSigned @p Int is
+/// interpreted as unsigned value or as signed value in two's complement
+/// representation.
+///
+/// Input IsSigned Output
+///
+/// 0 0 -> 0
+/// 1 0 -> 1
+/// 00 0 -> 0
+/// 01 0 -> 1
+/// 10 0 -> 2
+/// 11 0 -> 3
+///
+/// 0 1 -> 0
+/// 1 1 -> -1
+/// 00 1 -> 0
+/// 01 1 -> 1
+/// 10 1 -> -2
+/// 11 1 -> -1
+///
+/// @param Ctx The isl_ctx to create the isl_val in.
+/// @param Int The integer value to translate.
+/// @param IsSigned If the APInt should be interpreted as signed or unsigned
+/// value.
+///
+/// @return The isl_val corresponding to @p Int.
+__isl_give isl_val *isl_valFromAPInt(isl_ctx *Ctx, const llvm::APInt Int,
+ bool IsSigned);
+
+/// Translate an llvm::APInt to an isl::val.
+///
+/// Translate the bitsequence without sign information as provided by APInt into
+/// a signed isl::val type. Depending on the value of @p IsSigned @p Int is
+/// interpreted as unsigned value or as signed value in two's complement
+/// representation.
+///
+/// Input IsSigned Output
+///
+/// 0 0 -> 0
+/// 1 0 -> 1
+/// 00 0 -> 0
+/// 01 0 -> 1
+/// 10 0 -> 2
+/// 11 0 -> 3
+///
+/// 0 1 -> 0
+/// 1 1 -> -1
+/// 00 1 -> 0
+/// 01 1 -> 1
+/// 10 1 -> -2
+/// 11 1 -> -1
+///
+/// @param Ctx The isl_ctx to create the isl::val in.
+/// @param Int The integer value to translate.
+/// @param IsSigned If the APInt should be interpreted as signed or unsigned
+/// value.
+///
+/// @return The isl::val corresponding to @p Int.
+inline isl::val valFromAPInt(isl_ctx *Ctx, const llvm::APInt Int,
+ bool IsSigned) {
+ return isl::manage(isl_valFromAPInt(Ctx, Int, IsSigned));
+}
+
+/// Translate isl_val to llvm::APInt.
+///
+/// This function can only be called on isl_val values which are integers.
+/// Calling this function with a non-integral rational, NaN or infinity value
+/// is not allowed.
+///
+/// As the input isl_val may be negative, the APInt that this function returns
+/// must always be interpreted as signed two's complement value. The bitwidth of
+/// the generated APInt is always the minimal bitwidth necessary to model the
+/// provided integer when interpreting the bit pattern as signed value.
+///
+/// Some example conversions are:
+///
+/// Input Bits Signed Bitwidth
+/// 0 -> 0 0 1
+/// -1 -> 1 -1 1
+/// 1 -> 01 1 2
+/// -2 -> 10 -2 2
+/// 2 -> 010 2 3
+/// -3 -> 101 -3 3
+/// 3 -> 011 3 3
+/// -4 -> 100 -4 3
+/// 4 -> 0100 4 4
+///
+/// @param Val The isl val to translate.
+///
+/// @return The APInt value corresponding to @p Val.
+llvm::APInt APIntFromVal(__isl_take isl_val *Val);
+
+/// Translate isl::val to llvm::APInt.
+///
+/// This function can only be called on isl::val values which are integers.
+/// Calling this function with a non-integral rational, NaN or infinity value
+/// is not allowed.
+///
+/// As the input isl::val may be negative, the APInt that this function returns
+/// must always be interpreted as signed two's complement value. The bitwidth of
+/// the generated APInt is always the minimal bitwidth necessary to model the
+/// provided integer when interpreting the bit pattern as signed value.
+///
+/// Some example conversions are:
+///
+/// Input Bits Signed Bitwidth
+/// 0 -> 0 0 1
+/// -1 -> 1 -1 1
+/// 1 -> 01 1 2
+/// -2 -> 10 -2 2
+/// 2 -> 010 2 3
+/// -3 -> 101 -3 3
+/// 3 -> 011 3 3
+/// -4 -> 100 -4 3
+/// 4 -> 0100 4 4
+///
+/// @param Val The isl val to translate.
+///
+/// @return The APInt value corresponding to @p Val.
+inline llvm::APInt APIntFromVal(isl::val V) {
+ return APIntFromVal(V.release());
+}
+
+/// Get c++ string from Isl objects.
+//@{
+std::string stringFromIslObj(__isl_keep isl_map *map);
+std::string stringFromIslObj(__isl_keep isl_union_map *umap);
+std::string stringFromIslObj(__isl_keep isl_set *set);
+std::string stringFromIslObj(__isl_keep isl_union_set *uset);
+std::string stringFromIslObj(__isl_keep isl_schedule *schedule);
+std::string stringFromIslObj(__isl_keep isl_multi_aff *maff);
+std::string stringFromIslObj(__isl_keep isl_pw_multi_aff *pma);
+std::string stringFromIslObj(__isl_keep isl_multi_pw_aff *mpa);
+std::string stringFromIslObj(__isl_keep isl_union_pw_multi_aff *upma);
+std::string stringFromIslObj(__isl_keep isl_aff *aff);
+std::string stringFromIslObj(__isl_keep isl_pw_aff *pwaff);
+std::string stringFromIslObj(__isl_keep isl_space *space);
+//@}
+
+inline llvm::raw_ostream &operator<<(llvm::raw_ostream &OS,
+ __isl_keep isl_union_map *Map) {
+ OS << polly::stringFromIslObj(Map);
+ return OS;
+}
+
+inline llvm::raw_ostream &operator<<(llvm::raw_ostream &OS,
+ __isl_keep isl_map *Map) {
+ OS << polly::stringFromIslObj(Map);
+ return OS;
+}
+
+inline llvm::raw_ostream &operator<<(llvm::raw_ostream &OS,
+ __isl_keep isl_set *Set) {
+ OS << polly::stringFromIslObj(Set);
+ return OS;
+}
+
+inline llvm::raw_ostream &operator<<(llvm::raw_ostream &OS,
+ __isl_keep isl_pw_aff *Map) {
+ OS << polly::stringFromIslObj(Map);
+ return OS;
+}
+
+inline llvm::raw_ostream &operator<<(llvm::raw_ostream &OS,
+ __isl_keep isl_pw_multi_aff *PMA) {
+ OS << polly::stringFromIslObj(PMA);
+ return OS;
+}
+
+inline llvm::raw_ostream &operator<<(llvm::raw_ostream &OS,
+ __isl_keep isl_multi_aff *MA) {
+ OS << polly::stringFromIslObj(MA);
+ return OS;
+}
+
+inline llvm::raw_ostream &operator<<(llvm::raw_ostream &OS,
+ __isl_keep isl_union_pw_multi_aff *UPMA) {
+ OS << polly::stringFromIslObj(UPMA);
+ return OS;
+}
+
+inline llvm::raw_ostream &operator<<(llvm::raw_ostream &OS,
+ __isl_keep isl_schedule *Schedule) {
+ OS << polly::stringFromIslObj(Schedule);
+ return OS;
+}
+
+inline llvm::raw_ostream &operator<<(llvm::raw_ostream &OS,
+ __isl_keep isl_space *Space) {
+ OS << polly::stringFromIslObj(Space);
+ return OS;
+}
+
+/// Combine Prefix, Val (or Number) and Suffix to an isl-compatible name.
+///
+/// In case @p UseInstructionNames is set, this function returns:
+///
+/// @p Prefix + "_" + @p Val->getName() + @p Suffix
+///
+/// otherwise
+///
+/// @p Prefix + to_string(Number) + @p Suffix
+///
+/// We ignore the value names by default, as they may change between release
+/// and debug mode and can consequently not be used when aiming for reproducible
+/// builds. However, for debugging named statements are often helpful, hence
+/// we allow their optional use.
+std::string getIslCompatibleName(const std::string &Prefix,
+ const llvm::Value *Val, long Number,
+ const std::string &Suffix,
+ bool UseInstructionNames);
+
+/// Combine Prefix, Name (or Number) and Suffix to an isl-compatible name.
+///
+/// In case @p UseInstructionNames is set, this function returns:
+///
+/// @p Prefix + "_" + Name + @p Suffix
+///
+/// otherwise
+///
+/// @p Prefix + to_string(Number) + @p Suffix
+///
+/// We ignore @p Name by default, as they may change between release
+/// and debug mode and can consequently not be used when aiming for reproducible
+/// builds. However, for debugging named statements are often helpful, hence
+/// we allow their optional use.
+std::string getIslCompatibleName(const std::string &Prefix,
+ const std::string &Middle, long Number,
+ const std::string &Suffix,
+ bool UseInstructionNames);
+
+std::string getIslCompatibleName(const std::string &Prefix,
+ const std::string &Middle,
+ const std::string &Suffix);
+
+inline llvm::DiagnosticInfoOptimizationBase &
+operator<<(llvm::DiagnosticInfoOptimizationBase &OS,
+ const isl::union_map &Obj) {
+ OS << Obj.to_str();
+ return OS;
+}
+
+/// Scope guard for code that allows arbitrary isl function to return an error
+/// if the max-operations quota exceeds.
+///
+/// This allows to opt-in code sections that have known long executions times.
+/// code not in a hot path can continue to assume that no unexpected error
+/// occurs.
+///
+/// This is typically used inside a nested IslMaxOperationsGuard scope. The
+/// IslMaxOperationsGuard defines the number of allowed base operations for some
+/// code, IslQuotaScope defines where it is allowed to return an error result.
+class IslQuotaScope {
+ isl_ctx *IslCtx;
+ int OldOnError;
+
+public:
+ IslQuotaScope() : IslCtx(nullptr) {}
+ IslQuotaScope(const IslQuotaScope &) = delete;
+ IslQuotaScope(IslQuotaScope &&Other)
+ : IslCtx(Other.IslCtx), OldOnError(Other.OldOnError) {
+ Other.IslCtx = nullptr;
+ }
+ const IslQuotaScope &operator=(IslQuotaScope &&Other) {
+ std::swap(this->IslCtx, Other.IslCtx);
+ std::swap(this->OldOnError, Other.OldOnError);
+ return *this;
+ }
+
+ /// Enter a quota-aware scope.
+ ///
+ /// Should not be used directly. Use IslMaxOperationsGuard::enter() instead.
+ explicit IslQuotaScope(isl_ctx *IslCtx, unsigned long LocalMaxOps)
+ : IslCtx(IslCtx) {
+ assert(IslCtx);
+ assert(isl_ctx_get_max_operations(IslCtx) == 0 && "Incorrect nesting");
+ if (LocalMaxOps == 0) {
+ this->IslCtx = nullptr;
+ return;
+ }
+
+ OldOnError = isl_options_get_on_error(IslCtx);
+ isl_options_set_on_error(IslCtx, ISL_ON_ERROR_CONTINUE);
+ isl_ctx_reset_error(IslCtx);
+ isl_ctx_set_max_operations(IslCtx, LocalMaxOps);
+ }
+
+ ~IslQuotaScope() {
+ if (!IslCtx)
+ return;
+
+ assert(isl_ctx_get_max_operations(IslCtx) > 0 && "Incorrect nesting");
+ assert(isl_options_get_on_error(IslCtx) == ISL_ON_ERROR_CONTINUE &&
+ "Incorrect nesting");
+ isl_ctx_set_max_operations(IslCtx, 0);
+ isl_options_set_on_error(IslCtx, OldOnError);
+ }
+
+ /// Return whether the current quota has exceeded.
+ bool hasQuotaExceeded() const {
+ if (!IslCtx)
+ return false;
+
+ return isl_ctx_last_error(IslCtx) == isl_error_quota;
+ }
+};
+
+/// Scoped limit of ISL operations.
+///
+/// Limits the number of ISL operations during the lifetime of this object. The
+/// idea is to use this as an RAII guard for the scope where the code is aware
+/// that ISL can return errors even when all input is valid. After leaving the
+/// scope, it will return to the error setting as it was before. That also means
+/// that the error setting should not be changed while in that scope.
+///
+/// Such scopes are not allowed to be nested because the previous operations
+/// counter cannot be reset to the previous state, or one that adds the
+/// operations while being in the nested scope. Use therefore is only allowed
+/// while currently a no operations-limit is active.
+class IslMaxOperationsGuard {
+private:
+ /// The ISL context to set the operations limit.
+ ///
+ /// If set to nullptr, there is no need for any action at the end of the
+ /// scope.
+ isl_ctx *IslCtx;
+
+ /// Maximum number of operations for the scope.
+ unsigned long LocalMaxOps;
+
+ /// When AutoEnter is enabled, holds the IslQuotaScope object.
+ IslQuotaScope TopLevelScope;
+
+public:
+ /// Enter a max operations scope.
+ ///
+ /// @param IslCtx The ISL context to set the operations limit for.
+ /// @param LocalMaxOps Maximum number of operations allowed in the
+ /// scope. If set to zero, no operations limit is enforced.
+ /// @param AutoEnter If true, automatically enters an IslQuotaScope such
+ /// that isl operations may return quota errors
+ /// immediately. If false, only starts the operations
+ /// counter, but isl does not return quota errors before
+ /// calling enter().
+ IslMaxOperationsGuard(isl_ctx *IslCtx, unsigned long LocalMaxOps,
+ bool AutoEnter = true)
+ : IslCtx(IslCtx), LocalMaxOps(LocalMaxOps) {
+ assert(IslCtx);
+ assert(isl_ctx_get_max_operations(IslCtx) == 0 &&
+ "Nested max operations not supported");
+
+ // Users of this guard may check whether the last error was isl_error_quota.
+ // Reset the last error such that a previous out-of-quota error is not
+ // mistaken to have occurred in the in this quota, even if the max number of
+ // operations is set to infinite (LocalMaxOps == 0).
+ isl_ctx_reset_error(IslCtx);
+
+ if (LocalMaxOps == 0) {
+ // No limit on operations; also disable restoring on_error/max_operations.
+ this->IslCtx = nullptr;
+ return;
+ }
+
+ isl_ctx_reset_operations(IslCtx);
+ TopLevelScope = enter(AutoEnter);
+ }
+
+ /// Enter a scope that can handle out-of-quota errors.
+ ///
+ /// @param AllowReturnNull Whether the scoped code can handle out-of-quota
+ /// errors. If false, returns a dummy scope object that
+ /// does nothing.
+ IslQuotaScope enter(bool AllowReturnNull = true) {
+ return AllowReturnNull && IslCtx ? IslQuotaScope(IslCtx, LocalMaxOps)
+ : IslQuotaScope();
+ }
+
+ /// Return whether the current quota has exceeded.
+ bool hasQuotaExceeded() const {
+ if (!IslCtx)
+ return false;
+
+ return isl_ctx_last_error(IslCtx) == isl_error_quota;
+ }
+};
+} // end namespace polly
+
+#endif
diff --git a/linux-x64/clang/include/polly/Support/ISLOStream.h b/linux-x64/clang/include/polly/Support/ISLOStream.h
new file mode 100644
index 0000000..08853a2
--- /dev/null
+++ b/linux-x64/clang/include/polly/Support/ISLOStream.h
@@ -0,0 +1,47 @@
+//===------ IslOstream.h ----------------------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// raw_ostream printers for isl C++ objects.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Support/raw_ostream.h"
+#include "isl/isl-noexceptions.h"
+namespace polly {
+
+#define ADD_OSTREAM_PRINTER(name) \
+ inline llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, \
+ const name &Obj) { \
+ OS << Obj.to_str(); \
+ return OS; \
+ }
+
+ADD_OSTREAM_PRINTER(isl::aff)
+ADD_OSTREAM_PRINTER(isl::ast_expr)
+ADD_OSTREAM_PRINTER(isl::ast_node)
+ADD_OSTREAM_PRINTER(isl::basic_map)
+ADD_OSTREAM_PRINTER(isl::basic_set)
+ADD_OSTREAM_PRINTER(isl::map)
+ADD_OSTREAM_PRINTER(isl::set)
+ADD_OSTREAM_PRINTER(isl::id)
+ADD_OSTREAM_PRINTER(isl::multi_aff)
+ADD_OSTREAM_PRINTER(isl::multi_pw_aff)
+ADD_OSTREAM_PRINTER(isl::multi_union_pw_aff)
+ADD_OSTREAM_PRINTER(isl::point)
+ADD_OSTREAM_PRINTER(isl::pw_aff)
+ADD_OSTREAM_PRINTER(isl::pw_multi_aff)
+ADD_OSTREAM_PRINTER(isl::schedule)
+ADD_OSTREAM_PRINTER(isl::schedule_node)
+ADD_OSTREAM_PRINTER(isl::space)
+ADD_OSTREAM_PRINTER(isl::union_access_info)
+ADD_OSTREAM_PRINTER(isl::union_flow)
+ADD_OSTREAM_PRINTER(isl::union_set)
+ADD_OSTREAM_PRINTER(isl::union_map)
+ADD_OSTREAM_PRINTER(isl::union_pw_aff)
+ADD_OSTREAM_PRINTER(isl::union_pw_multi_aff)
+} // namespace polly
diff --git a/linux-x64/clang/include/polly/Support/ISLOperators.h b/linux-x64/clang/include/polly/Support/ISLOperators.h
new file mode 100644
index 0000000..28fee01
--- /dev/null
+++ b/linux-x64/clang/include/polly/Support/ISLOperators.h
@@ -0,0 +1,184 @@
+//===------ ISLOperators.h --------------------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// Operator overloads for isl C++ objects.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef POLLY_ISLOPERATORS_H
+#define POLLY_ISLOPERATORS_H
+
+#include "isl/isl-noexceptions.h"
+
+namespace polly {
+
+/// Addition
+/// @{
+inline isl::pw_aff operator+(isl::pw_aff Left, isl::pw_aff Right) {
+ return Left.add(Right);
+}
+
+inline isl::pw_aff operator+(isl::val ValLeft, isl::pw_aff Right) {
+ isl::pw_aff Left(Right.domain(), ValLeft);
+ return Left.add(Right);
+}
+
+inline isl::pw_aff operator+(isl::pw_aff Left, isl::val ValRight) {
+ isl::pw_aff Right(Left.domain(), ValRight);
+ return Left.add(Right);
+}
+
+inline isl::pw_aff operator+(long IntLeft, isl::pw_aff Right) {
+ isl::ctx Ctx = Right.get_ctx();
+ isl::val ValLeft(Ctx, IntLeft);
+ isl::pw_aff Left(Right.domain(), ValLeft);
+ return Left.add(Right);
+}
+
+inline isl::pw_aff operator+(isl::pw_aff Left, long IntRight) {
+ isl::ctx Ctx = Left.get_ctx();
+ isl::val ValRight(Ctx, IntRight);
+ isl::pw_aff Right(Left.domain(), ValRight);
+ return Left.add(Right);
+}
+/// @}
+
+/// Multiplication
+/// @{
+inline isl::pw_aff operator*(isl::pw_aff Left, isl::pw_aff Right) {
+ return Left.mul(Right);
+}
+
+inline isl::pw_aff operator*(isl::val ValLeft, isl::pw_aff Right) {
+ isl::pw_aff Left(Right.domain(), ValLeft);
+ return Left.mul(Right);
+}
+
+inline isl::pw_aff operator*(isl::pw_aff Left, isl::val ValRight) {
+ isl::pw_aff Right(Left.domain(), ValRight);
+ return Left.mul(Right);
+}
+
+inline isl::pw_aff operator*(long IntLeft, isl::pw_aff Right) {
+ isl::ctx Ctx = Right.get_ctx();
+ isl::val ValLeft(Ctx, IntLeft);
+ isl::pw_aff Left(Right.domain(), ValLeft);
+ return Left.mul(Right);
+}
+
+inline isl::pw_aff operator*(isl::pw_aff Left, long IntRight) {
+ isl::ctx Ctx = Left.get_ctx();
+ isl::val ValRight(Ctx, IntRight);
+ isl::pw_aff Right(Left.domain(), ValRight);
+ return Left.mul(Right);
+}
+/// @}
+
+/// Subtraction
+/// @{
+inline isl::pw_aff operator-(isl::pw_aff Left, isl::pw_aff Right) {
+ return Left.sub(Right);
+}
+
+inline isl::pw_aff operator-(isl::val ValLeft, isl::pw_aff Right) {
+ isl::pw_aff Left(Right.domain(), ValLeft);
+ return Left.sub(Right);
+}
+
+inline isl::pw_aff operator-(isl::pw_aff Left, isl::val ValRight) {
+ isl::pw_aff Right(Left.domain(), ValRight);
+ return Left.sub(Right);
+}
+
+inline isl::pw_aff operator-(long IntLeft, isl::pw_aff Right) {
+ isl::ctx Ctx = Right.get_ctx();
+ isl::val ValLeft(Ctx, IntLeft);
+ isl::pw_aff Left(Right.domain(), ValLeft);
+ return Left.sub(Right);
+}
+
+inline isl::pw_aff operator-(isl::pw_aff Left, long IntRight) {
+ isl::ctx Ctx = Left.get_ctx();
+ isl::val ValRight(Ctx, IntRight);
+ isl::pw_aff Right(Left.domain(), ValRight);
+ return Left.sub(Right);
+}
+/// @}
+
+/// Division
+///
+/// This division rounds towards zero. This follows the semantics of C/C++.
+///
+/// @{
+inline isl::pw_aff operator/(isl::pw_aff Left, isl::pw_aff Right) {
+ return Left.tdiv_q(Right);
+}
+
+inline isl::pw_aff operator/(isl::val ValLeft, isl::pw_aff Right) {
+ isl::pw_aff Left(Right.domain(), ValLeft);
+ return Left.tdiv_q(Right);
+}
+
+inline isl::pw_aff operator/(isl::pw_aff Left, isl::val ValRight) {
+ isl::pw_aff Right(Left.domain(), ValRight);
+ return Left.tdiv_q(Right);
+}
+
+inline isl::pw_aff operator/(long IntLeft, isl::pw_aff Right) {
+ isl::ctx Ctx = Right.get_ctx();
+ isl::val ValLeft(Ctx, IntLeft);
+ isl::pw_aff Left(Right.domain(), ValLeft);
+ return Left.tdiv_q(Right);
+}
+
+inline isl::pw_aff operator/(isl::pw_aff Left, long IntRight) {
+ isl::ctx Ctx = Left.get_ctx();
+ isl::val ValRight(Ctx, IntRight);
+ isl::pw_aff Right(Left.domain(), ValRight);
+ return Left.tdiv_q(Right);
+}
+/// @}
+
+/// Remainder
+///
+/// This is the remainder of a division which rounds towards zero. This follows
+/// the semantics of C/C++.
+///
+/// @{
+inline isl::pw_aff operator%(isl::pw_aff Left, isl::pw_aff Right) {
+ return Left.tdiv_r(Right);
+}
+
+inline isl::pw_aff operator%(isl::val ValLeft, isl::pw_aff Right) {
+ isl::pw_aff Left(Right.domain(), ValLeft);
+ return Left.tdiv_r(Right);
+}
+
+inline isl::pw_aff operator%(isl::pw_aff Left, isl::val ValRight) {
+ isl::pw_aff Right(Left.domain(), ValRight);
+ return Left.tdiv_r(Right);
+}
+
+inline isl::pw_aff operator%(long IntLeft, isl::pw_aff Right) {
+ isl::ctx Ctx = Right.get_ctx();
+ isl::val ValLeft(Ctx, IntLeft);
+ isl::pw_aff Left(Right.domain(), ValLeft);
+ return Left.tdiv_r(Right);
+}
+
+inline isl::pw_aff operator%(isl::pw_aff Left, long IntRight) {
+ isl::ctx Ctx = Left.get_ctx();
+ isl::val ValRight(Ctx, IntRight);
+ isl::pw_aff Right(Left.domain(), ValRight);
+ return Left.tdiv_r(Right);
+}
+/// @}
+
+} // namespace polly
+
+#endif // POLLY_ISLOPERATORS_H
diff --git a/linux-x64/clang/include/polly/Support/ISLTools.h b/linux-x64/clang/include/polly/Support/ISLTools.h
new file mode 100644
index 0000000..1e02831
--- /dev/null
+++ b/linux-x64/clang/include/polly/Support/ISLTools.h
@@ -0,0 +1,597 @@
+//===------ ISLTools.h ------------------------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// Tools, utilities, helpers and extensions useful in conjunction with the
+// Integer Set Library (isl).
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef POLLY_ISLTOOLS_H
+#define POLLY_ISLTOOLS_H
+
+#include "llvm/ADT/iterator.h"
+#include "isl/isl-noexceptions.h"
+
+namespace isl {
+inline namespace noexceptions {
+
+template <typename ListT>
+using list_element_type = decltype(std::declval<ListT>().get_at(0));
+
+template <typename ListT>
+struct isl_iterator
+ : public llvm::iterator_facade_base<isl_iterator<ListT>,
+ std::forward_iterator_tag,
+ list_element_type<ListT>> {
+
+ using ElementT = list_element_type<ListT>;
+
+ explicit isl_iterator(const ListT &List)
+ : List(&List), Position(std::max(List.size(), 0)) {}
+ isl_iterator(const ListT &List, int Position)
+ : List(&List), Position(Position) {}
+ isl_iterator &operator=(const isl_iterator &R) = default;
+
+ bool operator==(const isl_iterator &O) const {
+ return List == O.List && Position == O.Position;
+ }
+
+ isl_iterator &operator++() {
+ ++Position;
+ return *this;
+ }
+
+ isl_iterator operator++(int) {
+ isl_iterator Copy{*this};
+ ++Position;
+ return Copy;
+ }
+
+ ElementT operator*() const { return List->get_at(this->Position); }
+
+protected:
+ const ListT *List;
+ int Position = 0;
+};
+
+template <typename T> isl_iterator<T> begin(const T &t) {
+ return isl_iterator<T>(t, 0);
+}
+template <typename T> isl_iterator<T> end(const T &t) {
+ return isl_iterator<T>(t);
+}
+
+} // namespace noexceptions
+} // namespace isl
+
+namespace polly {
+
+/// Return the range elements that are lexicographically smaller.
+///
+/// @param Map { Space[] -> Scatter[] }
+/// @param Strict True for strictly lexicographically smaller elements (exclude
+/// same timepoints from the result).
+///
+/// @return { Space[] -> Scatter[] }
+/// A map to all timepoints that happen before the timepoints the input
+/// mapped to.
+isl::map beforeScatter(isl::map Map, bool Strict);
+
+/// Piecewise beforeScatter(isl::map,bool).
+isl::union_map beforeScatter(isl::union_map UMap, bool Strict);
+
+/// Return the range elements that are lexicographically larger.
+///
+/// @param Map { Space[] -> Scatter[] }
+/// @param Strict True for strictly lexicographically larger elements (exclude
+/// same timepoints from the result).
+///
+/// @return { Space[] -> Scatter[] }
+/// A map to all timepoints that happen after the timepoints the input
+/// map originally mapped to.
+isl::map afterScatter(isl::map Map, bool Strict);
+
+/// Piecewise afterScatter(isl::map,bool).
+isl::union_map afterScatter(const isl::union_map &UMap, bool Strict);
+
+/// Construct a range of timepoints between two timepoints.
+///
+/// Example:
+/// From := { A[] -> [0]; B[] -> [0] }
+/// To := { B[] -> [10]; C[] -> [20] }
+///
+/// Result:
+/// { B[] -> [i] : 0 < i < 10 }
+///
+/// Note that A[] and C[] are not in the result because they do not have a start
+/// or end timepoint. If a start (or end) timepoint is not unique, the first
+/// (respectively last) is chosen.
+///
+/// @param From { Space[] -> Scatter[] }
+/// Map to start timepoints.
+/// @param To { Space[] -> Scatter[] }
+/// Map to end timepoints.
+/// @param InclFrom Whether to include the start timepoints in the result. In
+/// the example, this would add { B[] -> [0] }
+/// @param InclTo Whether to include the end timepoints in the result. In this
+/// example, this would add { B[] -> [10] }
+///
+/// @return { Space[] -> Scatter[] }
+/// A map for each domain element of timepoints between two extreme
+/// points, or nullptr if @p From or @p To is nullptr, or the isl max
+/// operations is exceeded.
+isl::map betweenScatter(isl::map From, isl::map To, bool InclFrom, bool InclTo);
+
+/// Piecewise betweenScatter(isl::map,isl::map,bool,bool).
+isl::union_map betweenScatter(isl::union_map From, isl::union_map To,
+ bool InclFrom, bool InclTo);
+
+/// If by construction a union map is known to contain only a single map, return
+/// it.
+///
+/// This function combines isl_map_from_union_map() and
+/// isl_union_map_extract_map(). isl_map_from_union_map() fails if the map is
+/// empty because it does not know which space it would be in.
+/// isl_union_map_extract_map() on the other hand does not check whether there
+/// is (at most) one isl_map in the union, i.e. how it has been constructed is
+/// probably wrong.
+isl::map singleton(isl::union_map UMap, isl::space ExpectedSpace);
+
+/// If by construction an isl_union_set is known to contain only a single
+/// isl_set, return it.
+///
+/// This function combines isl_set_from_union_set() and
+/// isl_union_set_extract_set(). isl_map_from_union_set() fails if the set is
+/// empty because it does not know which space it would be in.
+/// isl_union_set_extract_set() on the other hand does not check whether there
+/// is (at most) one isl_set in the union, i.e. how it has been constructed is
+/// probably wrong.
+isl::set singleton(isl::union_set USet, isl::space ExpectedSpace);
+
+/// Determine how many dimensions the scatter space of @p Schedule has.
+///
+/// The schedule must not be empty and have equal number of dimensions of any
+/// subspace it contains.
+///
+/// The implementation currently returns the maximum number of dimensions it
+/// encounters, if different, and 0 if none is encountered. However, most other
+/// code will most likely fail if one of these happen.
+unsigned getNumScatterDims(const isl::union_map &Schedule);
+
+/// Return the scatter space of a @p Schedule.
+///
+/// This is basically the range space of the schedule map, but harder to
+/// determine because it is an isl_union_map.
+isl::space getScatterSpace(const isl::union_map &Schedule);
+
+/// Construct an identity map for the given domain values.
+///
+/// There is no type resembling isl_union_space, hence we have to pass an
+/// isl_union_set as the map's domain and range space.
+///
+/// @param USet { Space[] }
+/// The returned map's domain and range.
+/// @param RestrictDomain If true, the returned map only maps elements contained
+/// in @p USet and no other. If false, it returns an
+/// overapproximation with the identity maps of any space
+/// in @p USet, not just the elements in it.
+///
+/// @return { Space[] -> Space[] }
+/// A map that maps each value of @p USet to itself.
+isl::union_map makeIdentityMap(const isl::union_set &USet, bool RestrictDomain);
+
+/// Reverse the nested map tuple in @p Map's domain.
+///
+/// @param Map { [Space1[] -> Space2[]] -> Space3[] }
+///
+/// @return { [Space2[] -> Space1[]] -> Space3[] }
+isl::map reverseDomain(isl::map Map);
+
+/// Piecewise reverseDomain(isl::map).
+isl::union_map reverseDomain(const isl::union_map &UMap);
+
+/// Add a constant to one dimension of a set.
+///
+/// @param Map The set to shift a dimension in.
+/// @param Pos The dimension to shift. If negative, the dimensions are
+/// counted from the end instead from the beginning. E.g. -1 is
+/// the last dimension in the tuple.
+/// @param Amount The offset to add to the specified dimension.
+///
+/// @return The modified set.
+isl::set shiftDim(isl::set Set, int Pos, int Amount);
+
+/// Piecewise shiftDim(isl::set,int,int).
+isl::union_set shiftDim(isl::union_set USet, int Pos, int Amount);
+
+/// Add a constant to one dimension of a map.
+///
+/// @param Map The map to shift a dimension in.
+/// @param Type A tuple of @p Map which contains the dimension to shift.
+/// @param Pos The dimension to shift. If negative, the dimensions are
+/// counted from the end instead from the beginning. Eg. -1 is the last
+/// dimension in the tuple.
+/// @param Amount The offset to add to the specified dimension.
+///
+/// @return The modified map.
+isl::map shiftDim(isl::map Map, isl::dim Dim, int Pos, int Amount);
+
+/// Add a constant to one dimension of a each map in a union map.
+///
+/// @param UMap The maps to shift a dimension in.
+/// @param Type The tuple which contains the dimension to shift.
+/// @param Pos The dimension to shift. If negative, the dimensions are
+/// counted from the ends of each map of union instead from their
+/// beginning. E.g. -1 is the last dimension of any map.
+/// @param Amount The offset to add to the specified dimension.
+///
+/// @return The union of all modified maps.
+isl::union_map shiftDim(isl::union_map UMap, isl::dim Dim, int Pos, int Amount);
+
+/// Simplify a set inplace.
+void simplify(isl::set &Set);
+
+/// Simplify a union set inplace.
+void simplify(isl::union_set &USet);
+
+/// Simplify a map inplace.
+void simplify(isl::map &Map);
+
+/// Simplify a union map inplace.
+void simplify(isl::union_map &UMap);
+
+/// Compute the reaching definition statement or the next overwrite for each
+/// definition of an array element.
+///
+/// The reaching definition of an array element at a specific timepoint is the
+/// statement instance that has written the current element's content.
+/// Alternatively, this function determines for each timepoint and element which
+/// write is going to overwrite an element at a future timepoint. This can be
+/// seen as "reaching definition in reverse" where definitions are found in the
+/// past.
+///
+/// For example:
+///
+/// Schedule := { Write[] -> [0]; Overwrite[] -> [10] }
+/// Defs := { Write[] -> A[5]; Overwrite[] -> A[5] }
+///
+/// If index 5 of array A is written at timepoint 0 and 10, the resulting
+/// reaching definitions are:
+///
+/// { [A[5] -> [i]] -> Write[] : 0 < i < 10;
+/// [A[5] -> [i]] -> Overwrite[] : 10 < i }
+///
+/// Between timepoint 0 (Write[]) and timepoint 10 (Overwrite[]), the
+/// content of A[5] is written by statement instance Write[] and after
+/// timepoint 10 by Overwrite[]. Values not defined in the map have no known
+/// definition. This includes the statement instance timepoints themselves,
+/// because reads at those timepoints could either read the old or the new
+/// value, defined only by the statement itself. But this can be changed by @p
+/// InclPrevDef and @p InclNextDef. InclPrevDef=false and InclNextDef=true
+/// returns a zone. Unless @p InclPrevDef and @p InclNextDef are both true,
+/// there is only one unique definition per element and timepoint.
+///
+/// @param Schedule { DomainWrite[] -> Scatter[] }
+/// Schedule of (at least) all array writes. Instances not in
+/// @p Writes are ignored.
+/// @param Writes { DomainWrite[] -> Element[] }
+/// Elements written to by the statement instances.
+/// @param Reverse If true, look for definitions in the future. That is,
+/// find the write that is overwrites the current value.
+/// @param InclPrevDef Include the definition's timepoint to the set of
+/// well-defined elements (any load at that timepoint happen
+/// at the writes). In the example, enabling this option adds
+/// {[A[5] -> [0]] -> Write[]; [A[5] -> [10]] -> Overwrite[]}
+/// to the result.
+/// @param InclNextDef Whether to assume that at the timepoint where an element
+/// is overwritten, it still contains the old value (any load
+/// at that timepoint would happen before the overwrite). In
+/// this example, enabling this adds
+/// { [A[] -> [10]] -> Write[] } to the result.
+///
+/// @return { [Element[] -> Scatter[]] -> DomainWrite[] }
+/// The reaching definitions or future overwrite as described above, or
+/// nullptr if either @p Schedule or @p Writes is nullptr, or the isl
+/// max operations count has exceeded.
+isl::union_map computeReachingWrite(isl::union_map Schedule,
+ isl::union_map Writes, bool Reverse,
+ bool InclPrevDef, bool InclNextDef);
+
+/// Compute the timepoints where the contents of an array element are not used.
+///
+/// An element is unused at a timepoint when the element is overwritten in
+/// the future, but it is not read in between. Another way to express this: the
+/// time from when the element is written, to the most recent read before it, or
+/// infinitely into the past if there is no read before. Such unused elements
+/// can be overwritten by any value without changing the scop's semantics. An
+/// example:
+///
+/// Schedule := { Read[] -> [0]; Write[] -> [10]; Def[] -> [20] }
+/// Writes := { Write[] -> A[5]; Def[] -> A[6] }
+/// Reads := { Read[] -> A[5] }
+///
+/// The result is:
+///
+/// { A[5] -> [i] : 0 < i < 10;
+/// A[6] -> [i] : i < 20 }
+///
+/// That is, A[5] is unused between timepoint 0 (the read) and timepoint 10 (the
+/// write). A[6] is unused before timepoint 20, but might be used after the
+/// scop's execution (A[5] and any other A[i] as well). Use InclLastRead=false
+/// and InclWrite=true to interpret the result as zone.
+///
+/// @param Schedule { Domain[] -> Scatter[] }
+/// The schedule of (at least) all statement instances
+/// occurring in @p Writes or @p Reads. All other
+/// instances are ignored.
+/// @param Writes { DomainWrite[] -> Element[] }
+/// Elements written to by the statement instances.
+/// @param Reads { DomainRead[] -> Element[] }
+/// Elements read from by the statement instances.
+/// @param ReadEltInSameInst Whether a load reads the value from a write
+/// that is scheduled at the same timepoint (Writes
+/// happen before reads). Otherwise, loads use the
+/// value of an element that it had before the
+/// timepoint (Reads before writes). For example:
+/// { Read[] -> [0]; Write[] -> [0] }
+/// With ReadEltInSameInst=false it is assumed that the
+/// read happens before the write, such that the
+/// element is never unused, or just at timepoint 0,
+/// depending on InclLastRead/InclWrite.
+/// With ReadEltInSameInst=false it assumes that the
+/// value just written is used. Anything before
+/// timepoint 0 is considered unused.
+/// @param InclLastRead Whether a timepoint where an element is last read
+/// counts as unused (the read happens at the beginning
+/// of its timepoint, and nothing (else) can use it
+/// during the timepoint). In the example, this option
+/// adds { A[5] -> [0] } to the result.
+/// @param InclWrite Whether the timepoint where an element is written
+/// itself counts as unused (the write happens at the
+/// end of its timepoint; no (other) operations uses
+/// the element during the timepoint). In this example,
+/// this adds
+/// { A[5] -> [10]; A[6] -> [20] } to the result.
+///
+/// @return { Element[] -> Scatter[] }
+/// The unused timepoints as defined above, or nullptr if either @p
+/// Schedule, @p Writes are @p Reads is nullptr, or the ISL max
+/// operations count is exceeded.
+isl::union_map computeArrayUnused(isl::union_map Schedule,
+ isl::union_map Writes, isl::union_map Reads,
+ bool ReadEltInSameInst, bool InclLastRead,
+ bool InclWrite);
+
+/// Convert a zone (range between timepoints) to timepoints.
+///
+/// A zone represents the time between (integer) timepoints, but not the
+/// timepoints themselves. This function can be used to determine whether a
+/// timepoint lies within a zone.
+///
+/// For instance, the range (1,3), representing the time between 1 and 3, is
+/// represented by the zone
+///
+/// { [i] : 1 < i <= 3 }
+///
+/// The set of timepoints that lie completely within this range is
+///
+/// { [i] : 1 < i < 3 }
+///
+/// A typical use-case is the range in which a value written by a store is
+/// available until it is overwritten by another value. If the write is at
+/// timepoint 1 and its value is overwritten by another value at timepoint 3,
+/// the value is available between those timepoints: timepoint 2 in this
+/// example.
+///
+///
+/// When InclStart is true, the range is interpreted left-inclusive, i.e. adds
+/// the timepoint 1 to the result:
+///
+/// { [i] : 1 <= i < 3 }
+///
+/// In the use-case mentioned above that means that the value written at
+/// timepoint 1 is already available in timepoint 1 (write takes place before
+/// any read of it even if executed at the same timepoint)
+///
+/// When InclEnd is true, the range is interpreted right-inclusive, i.e. adds
+/// the timepoint 3 to the result:
+///
+/// { [i] : 1 < i <= 3 }
+///
+/// In the use-case mentioned above that means that although the value is
+/// overwritten in timepoint 3, the old value is still available at timepoint 3
+/// (write takes place after any read even if executed at the same timepoint)
+///
+/// @param Zone { Zone[] }
+/// @param InclStart Include timepoints adjacent to the beginning of a zone.
+/// @param InclEnd Include timepoints adjacent to the ending of a zone.
+///
+/// @return { Scatter[] }
+isl::union_set convertZoneToTimepoints(isl::union_set Zone, bool InclStart,
+ bool InclEnd);
+
+/// Like convertZoneToTimepoints(isl::union_set,InclStart,InclEnd), but convert
+/// either the domain or the range of a map.
+isl::union_map convertZoneToTimepoints(isl::union_map Zone, isl::dim Dim,
+ bool InclStart, bool InclEnd);
+
+/// Overload of convertZoneToTimepoints(isl::map,InclStart,InclEnd) to process
+/// only a single map.
+isl::map convertZoneToTimepoints(isl::map Zone, isl::dim Dim, bool InclStart,
+ bool InclEnd);
+
+/// Distribute the domain to the tuples of a wrapped range map.
+///
+/// @param Map { Domain[] -> [Range1[] -> Range2[]] }
+///
+/// @return { [Domain[] -> Range1[]] -> [Domain[] -> Range2[]] }
+isl::map distributeDomain(isl::map Map);
+
+/// Apply distributeDomain(isl::map) to each map in the union.
+isl::union_map distributeDomain(isl::union_map UMap);
+
+/// Prepend a space to the tuples of a map.
+///
+/// @param UMap { Domain[] -> Range[] }
+/// @param Factor { Factor[] }
+///
+/// @return { [Factor[] -> Domain[]] -> [Factor[] -> Range[]] }
+isl::union_map liftDomains(isl::union_map UMap, isl::union_set Factor);
+
+/// Apply a map to the 'middle' of another relation.
+///
+/// @param UMap { [DomainDomain[] -> DomainRange[]] -> Range[] }
+/// @param Func { DomainRange[] -> NewDomainRange[] }
+///
+/// @return { [DomainDomain[] -> NewDomainRange[]] -> Range[] }
+isl::union_map applyDomainRange(isl::union_map UMap, isl::union_map Func);
+
+/// Intersect the range of @p Map with @p Range.
+///
+/// Since @p Map is an isl::map, the result will be a single space, even though
+/// @p Range is an isl::union_set. This is the only difference to
+/// isl::map::intersect_range and isl::union_map::interset_range.
+///
+/// @param Map { Domain[] -> Range[] }
+/// @param Range { Range[] }
+///
+/// @return { Domain[] -> Range[] }
+isl::map intersectRange(isl::map Map, isl::union_set Range);
+
+/// Subtract the parameter space @p Params from @p Map.
+/// This is akin to isl::map::intersect_params.
+///
+/// Example:
+/// subtractParams(
+/// { [i] -> [i] },
+/// [x] -> { : x < 0 }
+/// ) = [x] -> { [i] -> [i] : x >= 0 }
+///
+/// @param Map Remove the conditions of @p Params from this map.
+/// @param Params Parameter set to subtract.
+///
+/// @param The map with the parameter conditions removed.
+isl::map subtractParams(isl::map Map, isl::set Params);
+
+/// Subtract the parameter space @p Params from @p Set.
+isl::set subtractParams(isl::set Set, isl::set Params);
+
+/// If @p PwAff maps to a constant, return said constant. If @p Max/@p Min, it
+/// can also be a piecewise constant and it would return the minimum/maximum
+/// value. Otherwise, return NaN.
+isl::val getConstant(isl::pw_aff PwAff, bool Max, bool Min);
+
+/// Dump a description of the argument to llvm::errs().
+///
+/// In contrast to isl's dump function, there are a few differences:
+/// - Each polyhedron (pieces) is written on its own line.
+/// - Spaces are sorted by structure. E.g. maps with same domain space are
+/// grouped. Isl sorts them according to the space's hash function.
+/// - Pieces of the same space are sorted using their lower bound.
+/// - A more compact to_str representation is used instead of Isl's dump
+/// functions that try to show the internal representation.
+///
+/// The goal is to get a better understandable representation that is also
+/// useful to compare two sets. As all dump() functions, its intended use is to
+/// be called in a debugger only.
+///
+/// isl_map_dump example:
+/// [p_0, p_1, p_2] -> { Stmt0[i0] -> [o0, o1] : (o0 = i0 and o1 = 0 and i0 > 0
+/// and i0 <= 5 - p_2) or (i0 = 0 and o0 = 0 and o1 = 0); Stmt3[i0] -> [o0, o1]
+/// : (o0 = i0 and o1 = 3 and i0 > 0 and i0 <= 5 - p_2) or (i0 = 0 and o0 = 0
+/// and o1 = 3); Stmt2[i0] -> [o0, o1] : (o0 = i0 and o1 = 1 and i0 >= 3 + p_0 -
+/// p_1 and i0 > 0 and i0 <= 5 - p_2) or (o0 = i0 and o1 = 1 and i0 > 0 and i0
+/// <= 5 - p_2 and i0 < p_0 - p_1) or (i0 = 0 and o0 = 0 and o1 = 1 and p_1 >= 3
+/// + p_0) or (i0 = 0 and o0 = 0 and o1 = 1 and p_1 < p_0) or (p_0 = 0 and i0 =
+/// 2 - p_1 and o0 = 2 - p_1 and o1 = 1 and p_2 <= 3 + p_1 and p_1 <= 1) or (p_1
+/// = 1 + p_0 and i0 = 0 and o0 = 0 and o1 = 1) or (p_0 = 0 and p_1 = 2 and i0 =
+/// 0 and o0 = 0 and o1 = 1) or (p_0 = -1 and p_1 = -1 and i0 = 0 and o0 = 0 and
+/// o1 = 1); Stmt1[i0] -> [o0, o1] : (p_0 = -1 and i0 = 1 - p_1 and o0 = 1 - p_1
+/// and o1 = 2 and p_2 <= 4 + p_1 and p_1 <= 0) or (p_0 = 0 and i0 = -p_1 and o0
+/// = -p_1 and o1 = 2 and p_2 <= 5 + p_1 and p_1 < 0) or (p_0 = -1 and p_1 = 1
+/// and i0 = 0 and o0 = 0 and o1 = 2) or (p_0 = 0 and p_1 = 0 and i0 = 0 and o0
+/// = 0 and o1 = 2) }
+///
+/// dumpPw example (same set):
+/// [p_0, p_1, p_2] -> {
+/// Stmt0[0] -> [0, 0];
+/// Stmt0[i0] -> [i0, 0] : 0 < i0 <= 5 - p_2;
+/// Stmt1[0] -> [0, 2] : p_1 = 1 and p_0 = -1;
+/// Stmt1[0] -> [0, 2] : p_1 = 0 and p_0 = 0;
+/// Stmt1[1 - p_1] -> [1 - p_1, 2] : p_0 = -1 and p_1 <= 0 and p_2 <= 4 + p_1;
+/// Stmt1[-p_1] -> [-p_1, 2] : p_0 = 0 and p_1 < 0 and p_2 <= 5 + p_1;
+/// Stmt2[0] -> [0, 1] : p_1 >= 3 + p_0;
+/// Stmt2[0] -> [0, 1] : p_1 < p_0;
+/// Stmt2[0] -> [0, 1] : p_1 = 1 + p_0;
+/// Stmt2[0] -> [0, 1] : p_1 = 2 and p_0 = 0;
+/// Stmt2[0] -> [0, 1] : p_1 = -1 and p_0 = -1;
+/// Stmt2[i0] -> [i0, 1] : i0 >= 3 + p_0 - p_1 and 0 < i0 <= 5 - p_2;
+/// Stmt2[i0] -> [i0, 1] : 0 < i0 <= 5 - p_2 and i0 < p_0 - p_1;
+/// Stmt2[2 - p_1] -> [2 - p_1, 1] : p_0 = 0 and p_1 <= 1 and p_2 <= 3 + p_1;
+/// Stmt3[0] -> [0, 3];
+/// Stmt3[i0] -> [i0, 3] : 0 < i0 <= 5 - p_2
+/// }
+/// @{
+void dumpPw(const isl::set &Set);
+void dumpPw(const isl::map &Map);
+void dumpPw(const isl::union_set &USet);
+void dumpPw(const isl::union_map &UMap);
+void dumpPw(__isl_keep isl_set *Set);
+void dumpPw(__isl_keep isl_map *Map);
+void dumpPw(__isl_keep isl_union_set *USet);
+void dumpPw(__isl_keep isl_union_map *UMap);
+/// @}
+
+/// Dump all points of the argument to llvm::errs().
+///
+/// Before being printed by dumpPw(), the argument's pieces are expanded to
+/// contain only single points. If a dimension is unbounded, it keeps its
+/// representation.
+///
+/// This is useful for debugging reduced cases where parameters are set to
+/// constants to keep the example simple. Such sets can still contain
+/// existential dimensions which makes the polyhedral hard to compare.
+///
+/// Example:
+/// { [MemRef_A[i0] -> [i1]] : (exists (e0 = floor((1 + i1)/3): i0 = 1 and 3e0
+/// <= i1 and 3e0 >= -1 + i1 and i1 >= 15 and i1 <= 25)) or (exists (e0 =
+/// floor((i1)/3): i0 = 0 and 3e0 < i1 and 3e0 >= -2 + i1 and i1 > 0 and i1 <=
+/// 11)) }
+///
+/// dumpExpanded:
+/// {
+/// [MemRef_A[0] ->[1]];
+/// [MemRef_A[0] ->[2]];
+/// [MemRef_A[0] ->[4]];
+/// [MemRef_A[0] ->[5]];
+/// [MemRef_A[0] ->[7]];
+/// [MemRef_A[0] ->[8]];
+/// [MemRef_A[0] ->[10]];
+/// [MemRef_A[0] ->[11]];
+/// [MemRef_A[1] ->[15]];
+/// [MemRef_A[1] ->[16]];
+/// [MemRef_A[1] ->[18]];
+/// [MemRef_A[1] ->[19]];
+/// [MemRef_A[1] ->[21]];
+/// [MemRef_A[1] ->[22]];
+/// [MemRef_A[1] ->[24]];
+/// [MemRef_A[1] ->[25]]
+/// }
+/// @{
+void dumpExpanded(const isl::set &Set);
+void dumpExpanded(const isl::map &Map);
+void dumpExpanded(const isl::union_set &USet);
+void dumpExpanded(const isl::union_map &UMap);
+void dumpExpanded(__isl_keep isl_set *Set);
+void dumpExpanded(__isl_keep isl_map *Map);
+void dumpExpanded(__isl_keep isl_union_set *USet);
+void dumpExpanded(__isl_keep isl_union_map *UMap);
+/// @}
+} // namespace polly
+
+#endif /* POLLY_ISLTOOLS_H */
diff --git a/linux-x64/clang/include/polly/Support/LinkGPURuntime.h b/linux-x64/clang/include/polly/Support/LinkGPURuntime.h
new file mode 100644
index 0000000..c632d45
--- /dev/null
+++ b/linux-x64/clang/include/polly/Support/LinkGPURuntime.h
@@ -0,0 +1,42 @@
+//===- Support/LinkGPURuntime.h -- Headerfile to help force-link GPURuntime =//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This header helps pull in libGPURuntime.so
+//
+//===----------------------------------------------------------------------===//
+#ifndef POLLY_LINK_GPURUNTIME
+#define POLLY_LINK_GPURUNTIME
+
+extern "C" {
+#include "GPURuntime/GPUJIT.h"
+}
+
+namespace polly {
+struct ForceGPURuntimeLinking {
+ ForceGPURuntimeLinking() {
+ if (std::getenv("bar") != (char *)-1)
+ return;
+ // We must reference GPURuntime in such a way that compilers will not
+ // delete it all as dead code, even with whole program optimization,
+ // yet is effectively a NO-OP. As the compiler isn't smart enough
+ // to know that getenv() never returns -1, this will do the job.
+ polly_initContextCL();
+ polly_initContextCUDA();
+ polly_getKernel(nullptr, nullptr);
+ polly_freeKernel(nullptr);
+ polly_copyFromHostToDevice(nullptr, nullptr, 0);
+ polly_copyFromDeviceToHost(nullptr, nullptr, 0);
+ polly_synchronizeDevice();
+ polly_launchKernel(nullptr, 0, 0, 0, 0, 0, nullptr);
+ polly_freeDeviceMemory(nullptr);
+ polly_freeContext(nullptr);
+ polly_synchronizeDevice();
+ }
+} structure;
+} // namespace polly
+#endif
diff --git a/linux-x64/clang/include/polly/Support/SCEVAffinator.h b/linux-x64/clang/include/polly/Support/SCEVAffinator.h
new file mode 100644
index 0000000..f5d7711
--- /dev/null
+++ b/linux-x64/clang/include/polly/Support/SCEVAffinator.h
@@ -0,0 +1,123 @@
+//===------ polly/SCEVAffinator.h - Create isl expressions from SCEVs -----===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// Create a polyhedral description for a SCEV value.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef POLLY_SCEV_AFFINATOR_H
+#define POLLY_SCEV_AFFINATOR_H
+
+#include "polly/Support/ScopHelper.h"
+#include "llvm/Analysis/ScalarEvolutionExpressions.h"
+#include "isl/isl-noexceptions.h"
+
+namespace polly {
+class Scop;
+
+/// The result type of the SCEVAffinator.
+///
+/// The first element of the pair is the isl representation of the SCEV, the
+/// second is the domain under which it is __invalid__.
+typedef std::pair<isl::pw_aff, isl::set> PWACtx;
+
+/// Translate a SCEV to an isl::pw_aff and the domain on which it is invalid.
+struct SCEVAffinator : public llvm::SCEVVisitor<SCEVAffinator, PWACtx> {
+public:
+ SCEVAffinator(Scop *S, llvm::LoopInfo &LI);
+
+ /// Translate a SCEV to an isl::pw_aff.
+ ///
+ /// @param E he expression that is translated.
+ /// @param BB The block in which @p E is executed.
+ ///
+ /// @returns The isl representation of the SCEV @p E in @p Domain.
+ PWACtx getPwAff(const llvm::SCEV *E, llvm::BasicBlock *BB = nullptr,
+ RecordedAssumptionsTy *RecordedAssumptions = nullptr);
+
+ /// Take the assumption that @p PWAC is non-negative.
+ void takeNonNegativeAssumption(
+ PWACtx &PWAC, RecordedAssumptionsTy *RecordedAssumptions = nullptr);
+
+ /// Interpret the PWA in @p PWAC as an unsigned value.
+ void interpretAsUnsigned(PWACtx &PWAC, unsigned Width);
+
+ /// Check an <nsw> AddRec for the loop @p L is cached.
+ bool hasNSWAddRecForLoop(llvm::Loop *L) const;
+
+ /// Return the LoopInfo used by thi object.
+ llvm::LoopInfo *getLI() const { return &LI; }
+
+private:
+ /// Key to identify cached expressions.
+ using CacheKey = std::pair<const llvm::SCEV *, llvm::BasicBlock *>;
+
+ /// Map to remembered cached expressions.
+ llvm::DenseMap<CacheKey, PWACtx> CachedExpressions;
+
+ Scop *S;
+ isl::ctx Ctx;
+ unsigned NumIterators;
+ llvm::ScalarEvolution &SE;
+ llvm::LoopInfo &LI;
+ llvm::BasicBlock *BB;
+ RecordedAssumptionsTy *RecordedAssumptions = nullptr;
+
+ /// Target data for element size computing.
+ const llvm::DataLayout &TD;
+
+ /// Return the loop for the current block if any.
+ llvm::Loop *getScope();
+
+ /// Return a PWACtx for @p PWA that is always valid.
+ PWACtx getPWACtxFromPWA(isl::pw_aff PWA);
+
+ /// Compute the non-wrapping version of @p PWA for type @p ExprType.
+ ///
+ /// @param PWA The piece-wise affine function that might wrap.
+ /// @param Type The type of the SCEV that was translated to @p PWA.
+ ///
+ /// @returns The expr @p PWA modulo the size constraints of @p ExprType.
+ isl::pw_aff addModuloSemantic(isl::pw_aff PWA, llvm::Type *ExprType) const;
+
+ /// If @p Expr might cause an integer wrap record an assumption.
+ ///
+ /// @param Expr The SCEV expression that might wrap.
+ /// @param PWAC The isl representation of @p Expr with the invalid domain.
+ ///
+ /// @returns The isl representation @p PWAC with a possibly adjusted domain.
+ PWACtx checkForWrapping(const llvm::SCEV *Expr, PWACtx PWAC) const;
+
+ /// Whether to track the value of this expression precisely, rather than
+ /// assuming it won't wrap.
+ bool computeModuloForExpr(const llvm::SCEV *Expr);
+
+ PWACtx visit(const llvm::SCEV *E);
+ PWACtx visitConstant(const llvm::SCEVConstant *E);
+ PWACtx visitPtrToIntExpr(const llvm::SCEVPtrToIntExpr *E);
+ PWACtx visitTruncateExpr(const llvm::SCEVTruncateExpr *E);
+ PWACtx visitZeroExtendExpr(const llvm::SCEVZeroExtendExpr *E);
+ PWACtx visitSignExtendExpr(const llvm::SCEVSignExtendExpr *E);
+ PWACtx visitAddExpr(const llvm::SCEVAddExpr *E);
+ PWACtx visitMulExpr(const llvm::SCEVMulExpr *E);
+ PWACtx visitUDivExpr(const llvm::SCEVUDivExpr *E);
+ PWACtx visitAddRecExpr(const llvm::SCEVAddRecExpr *E);
+ PWACtx visitSMaxExpr(const llvm::SCEVSMaxExpr *E);
+ PWACtx visitSMinExpr(const llvm::SCEVSMinExpr *E);
+ PWACtx visitUMaxExpr(const llvm::SCEVUMaxExpr *E);
+ PWACtx visitUMinExpr(const llvm::SCEVUMinExpr *E);
+ PWACtx visitUnknown(const llvm::SCEVUnknown *E);
+ PWACtx visitSDivInstruction(llvm::Instruction *SDiv);
+ PWACtx visitSRemInstruction(llvm::Instruction *SRem);
+ PWACtx complexityBailout();
+
+ friend struct llvm::SCEVVisitor<SCEVAffinator, PWACtx>;
+};
+} // namespace polly
+
+#endif
diff --git a/linux-x64/clang/include/polly/Support/SCEVValidator.h b/linux-x64/clang/include/polly/Support/SCEVValidator.h
new file mode 100644
index 0000000..a341dc0
--- /dev/null
+++ b/linux-x64/clang/include/polly/Support/SCEVValidator.h
@@ -0,0 +1,110 @@
+//===--- SCEVValidator.h - Detect Scops -------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+// Checks if a SCEV expression represents a valid affine expression.
+//===----------------------------------------------------------------------===//
+
+#ifndef POLLY_SCEV_VALIDATOR_H
+#define POLLY_SCEV_VALIDATOR_H
+
+#include "polly/Support/ScopHelper.h"
+
+namespace llvm {
+class SCEVConstant;
+} // namespace llvm
+
+namespace polly {
+
+/// Check if a call is side-effect free and has only constant arguments.
+///
+/// Such calls can be re-generated easily, so we do not need to model them
+/// as scalar dependences.
+///
+/// @param Call The call to check.
+bool isConstCall(llvm::CallInst *Call);
+
+/// Check if some parameters in the affine expression might hide induction
+/// variables. If this is the case, we will try to delinearize the accesses
+/// taking into account this information to possibly obtain a memory access
+/// with more structure. Currently we assume that each parameter that
+/// comes from a function call might depend on a (virtual) induction variable.
+/// This covers calls to 'get_global_id' and 'get_local_id' as they commonly
+/// arise in OpenCL code, while not catching any false-positives in our current
+/// tests.
+bool hasIVParams(const llvm::SCEV *Expr);
+
+/// Find the loops referenced from a SCEV expression.
+///
+/// @param Expr The SCEV expression to scan for loops.
+/// @param Loops A vector into which the found loops are inserted.
+void findLoops(const llvm::SCEV *Expr,
+ llvm::SetVector<const llvm::Loop *> &Loops);
+
+/// Find the values referenced by SCEVUnknowns in a given SCEV
+/// expression.
+///
+/// @param Expr The SCEV expression to scan for SCEVUnknowns.
+/// @param SE The ScalarEvolution analysis for this function.
+/// @param Values A vector into which the found values are inserted.
+void findValues(const llvm::SCEV *Expr, llvm::ScalarEvolution &SE,
+ llvm::SetVector<llvm::Value *> &Values);
+
+/// Returns true when the SCEV contains references to instructions within the
+/// region.
+///
+/// @param Expr The SCEV to analyze.
+/// @param R The region in which we look for dependences.
+/// @param Scope Location where the value is needed.
+/// @param AllowLoops Whether loop recurrences outside the loop that are in the
+/// region count as dependence.
+bool hasScalarDepsInsideRegion(const llvm::SCEV *Expr, const llvm::Region *R,
+ llvm::Loop *Scope, bool AllowLoops,
+ const InvariantLoadsSetTy &ILS);
+bool isAffineExpr(const llvm::Region *R, llvm::Loop *Scope,
+ const llvm::SCEV *Expression, llvm::ScalarEvolution &SE,
+ InvariantLoadsSetTy *ILS = nullptr);
+
+/// Check if @p V describes an affine constraint in @p R.
+bool isAffineConstraint(llvm::Value *V, const llvm::Region *R,
+ llvm::Loop *Scope, llvm::ScalarEvolution &SE,
+ ParameterSetTy &Params, bool OrExpr = false);
+
+ParameterSetTy getParamsInAffineExpr(const llvm::Region *R, llvm::Loop *Scope,
+ const llvm::SCEV *Expression,
+ llvm::ScalarEvolution &SE);
+
+/// Extract the constant factors from the multiplication @p M.
+///
+/// @param M A potential SCEV multiplication.
+/// @param SE The ScalarEvolution analysis to create new SCEVs.
+///
+/// @returns The constant factor in @p M and the rest of @p M.
+std::pair<const llvm::SCEVConstant *, const llvm::SCEV *>
+extractConstantFactor(const llvm::SCEV *M, llvm::ScalarEvolution &SE);
+
+/// Try to look through PHI nodes, where some incoming edges come from error
+/// blocks.
+///
+/// In case a PHI node follows an error block we can assume that the incoming
+/// value can only come from the node that is not an error block. As a result,
+/// conditions that seemed non-affine before are now in fact affine.
+const llvm::SCEV *tryForwardThroughPHI(const llvm::SCEV *Expr, llvm::Region &R,
+ llvm::ScalarEvolution &SE,
+ llvm::LoopInfo &LI,
+ const llvm::DominatorTree &DT);
+
+/// Return a unique non-error block incoming value for @p PHI if available.
+///
+/// @param R The region to run our code on.
+/// @param LI The loopinfo tree
+/// @param DT The dominator tree
+llvm::Value *getUniqueNonErrorValue(llvm::PHINode *PHI, llvm::Region *R,
+ llvm::LoopInfo &LI,
+ const llvm::DominatorTree &DT);
+} // namespace polly
+
+#endif
diff --git a/linux-x64/clang/include/polly/Support/ScopHelper.h b/linux-x64/clang/include/polly/Support/ScopHelper.h
new file mode 100644
index 0000000..4adf953
--- /dev/null
+++ b/linux-x64/clang/include/polly/Support/ScopHelper.h
@@ -0,0 +1,543 @@
+//===------ Support/ScopHelper.h -- Some Helper Functions for Scop. -------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// Small functions that help with LLVM-IR.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef POLLY_SUPPORT_IRHELPER_H
+#define POLLY_SUPPORT_IRHELPER_H
+
+#include "llvm/ADT/SetVector.h"
+#include "llvm/IR/Instructions.h"
+#include "llvm/IR/IntrinsicInst.h"
+#include "llvm/IR/ValueHandle.h"
+#include "isl/isl-noexceptions.h"
+
+namespace llvm {
+class LoopInfo;
+class Loop;
+class ScalarEvolution;
+class SCEV;
+class Region;
+class Pass;
+class DominatorTree;
+class RegionInfo;
+class RegionNode;
+} // namespace llvm
+
+namespace polly {
+class Scop;
+class ScopStmt;
+
+/// Enumeration of assumptions Polly can take.
+enum AssumptionKind {
+ ALIASING,
+ INBOUNDS,
+ WRAPPING,
+ UNSIGNED,
+ PROFITABLE,
+ ERRORBLOCK,
+ COMPLEXITY,
+ INFINITELOOP,
+ INVARIANTLOAD,
+ DELINEARIZATION,
+};
+
+/// Enum to distinguish between assumptions and restrictions.
+enum AssumptionSign { AS_ASSUMPTION, AS_RESTRICTION };
+
+/// Helper struct to remember assumptions.
+struct Assumption {
+ /// The kind of the assumption (e.g., WRAPPING).
+ AssumptionKind Kind;
+
+ /// Flag to distinguish assumptions and restrictions.
+ AssumptionSign Sign;
+
+ /// The valid/invalid context if this is an assumption/restriction.
+ isl::set Set;
+
+ /// The location that caused this assumption.
+ llvm::DebugLoc Loc;
+
+ /// An optional block whose domain can simplify the assumption.
+ llvm::BasicBlock *BB;
+};
+
+using RecordedAssumptionsTy = llvm::SmallVector<Assumption, 8>;
+
+/// Record an assumption for later addition to the assumed context.
+///
+/// This function will add the assumption to the RecordedAssumptions. This
+/// collection will be added (@see addAssumption) to the assumed context once
+/// all paramaters are known and the context is fully built.
+///
+/// @param RecordedAssumption container which keeps all recorded assumptions.
+/// @param Kind The assumption kind describing the underlying cause.
+/// @param Set The relations between parameters that are assumed to hold.
+/// @param Loc The location in the source that caused this assumption.
+/// @param Sign Enum to indicate if the assumptions in @p Set are positive
+/// (needed/assumptions) or negative (invalid/restrictions).
+/// @param BB The block in which this assumption was taken. If it is
+/// set, the domain of that block will be used to simplify the
+/// actual assumption in @p Set once it is added. This is useful
+/// if the assumption was created prior to the domain.
+void recordAssumption(RecordedAssumptionsTy *RecordedAssumptions,
+ AssumptionKind Kind, isl::set Set, llvm::DebugLoc Loc,
+ AssumptionSign Sign, llvm::BasicBlock *BB = nullptr);
+
+/// Type to remap values.
+using ValueMapT = llvm::DenseMap<llvm::AssertingVH<llvm::Value>,
+ llvm::AssertingVH<llvm::Value>>;
+
+/// Type for a set of invariant loads.
+using InvariantLoadsSetTy = llvm::SetVector<llvm::AssertingVH<llvm::LoadInst>>;
+
+/// Set type for parameters.
+using ParameterSetTy = llvm::SetVector<const llvm::SCEV *>;
+
+/// Set of loops (used to remember loops in non-affine subregions).
+using BoxedLoopsSetTy = llvm::SetVector<const llvm::Loop *>;
+
+/// Utility proxy to wrap the common members of LoadInst and StoreInst.
+///
+/// This works like the LLVM utility class CallSite, ie. it forwards all calls
+/// to either a LoadInst, StoreInst, MemIntrinsic or MemTransferInst.
+/// It is similar to LLVM's utility classes IntrinsicInst, MemIntrinsic,
+/// MemTransferInst, etc. in that it offers a common interface, but does not act
+/// as a fake base class.
+/// It is similar to StringRef and ArrayRef in that it holds a pointer to the
+/// referenced object and should be passed by-value as it is small enough.
+///
+/// This proxy can either represent a LoadInst instance, a StoreInst instance,
+/// a MemIntrinsic instance (memset, memmove, memcpy), a CallInst instance or a
+/// nullptr (only creatable using the default constructor); never an Instruction
+/// that is neither of the above mentioned. When representing a nullptr, only
+/// the following methods are defined:
+/// isNull(), isInstruction(), isLoad(), isStore(), ..., isMemTransferInst(),
+/// operator bool(), operator!()
+///
+/// The functions isa, cast, cast_or_null, dyn_cast are modeled te resemble
+/// those from llvm/Support/Casting.h. Partial template function specialization
+/// is currently not supported in C++ such that those cannot be used directly.
+/// (llvm::isa could, but then llvm:cast etc. would not have the expected
+/// behavior)
+class MemAccInst {
+private:
+ llvm::Instruction *I;
+
+public:
+ MemAccInst() : I(nullptr) {}
+ MemAccInst(const MemAccInst &Inst) : I(Inst.I) {}
+ /* implicit */ MemAccInst(llvm::LoadInst &LI) : I(&LI) {}
+ /* implicit */ MemAccInst(llvm::LoadInst *LI) : I(LI) {}
+ /* implicit */ MemAccInst(llvm::StoreInst &SI) : I(&SI) {}
+ /* implicit */ MemAccInst(llvm::StoreInst *SI) : I(SI) {}
+ /* implicit */ MemAccInst(llvm::MemIntrinsic *MI) : I(MI) {}
+ /* implicit */ MemAccInst(llvm::CallInst *CI) : I(CI) {}
+ explicit MemAccInst(llvm::Instruction &I) : I(&I) { assert(isa(I)); }
+ explicit MemAccInst(llvm::Instruction *I) : I(I) { assert(isa(I)); }
+
+ static bool isa(const llvm::Value &V) {
+ return llvm::isa<llvm::LoadInst>(V) || llvm::isa<llvm::StoreInst>(V) ||
+ llvm::isa<llvm::CallInst>(V) || llvm::isa<llvm::MemIntrinsic>(V);
+ }
+ static bool isa(const llvm::Value *V) {
+ return llvm::isa<llvm::LoadInst>(V) || llvm::isa<llvm::StoreInst>(V) ||
+ llvm::isa<llvm::CallInst>(V) || llvm::isa<llvm::MemIntrinsic>(V);
+ }
+ static MemAccInst cast(llvm::Value &V) {
+ return MemAccInst(llvm::cast<llvm::Instruction>(V));
+ }
+ static MemAccInst cast(llvm::Value *V) {
+ return MemAccInst(llvm::cast<llvm::Instruction>(V));
+ }
+ static MemAccInst cast_or_null(llvm::Value &V) {
+ return MemAccInst(llvm::cast<llvm::Instruction>(V));
+ }
+ static MemAccInst cast_or_null(llvm::Value *V) {
+ if (!V)
+ return MemAccInst();
+ return MemAccInst(llvm::cast<llvm::Instruction>(V));
+ }
+ static MemAccInst dyn_cast(llvm::Value &V) {
+ if (isa(V))
+ return MemAccInst(llvm::cast<llvm::Instruction>(V));
+ return MemAccInst();
+ }
+ static MemAccInst dyn_cast(llvm::Value *V) {
+ assert(V);
+ if (isa(V))
+ return MemAccInst(llvm::cast<llvm::Instruction>(V));
+ return MemAccInst();
+ }
+
+ MemAccInst &operator=(const MemAccInst &Inst) {
+ I = Inst.I;
+ return *this;
+ }
+ MemAccInst &operator=(llvm::LoadInst &LI) {
+ I = &LI;
+ return *this;
+ }
+ MemAccInst &operator=(llvm::LoadInst *LI) {
+ I = LI;
+ return *this;
+ }
+ MemAccInst &operator=(llvm::StoreInst &SI) {
+ I = &SI;
+ return *this;
+ }
+ MemAccInst &operator=(llvm::StoreInst *SI) {
+ I = SI;
+ return *this;
+ }
+ MemAccInst &operator=(llvm::MemIntrinsic &MI) {
+ I = &MI;
+ return *this;
+ }
+ MemAccInst &operator=(llvm::MemIntrinsic *MI) {
+ I = MI;
+ return *this;
+ }
+ MemAccInst &operator=(llvm::CallInst &CI) {
+ I = &CI;
+ return *this;
+ }
+ MemAccInst &operator=(llvm::CallInst *CI) {
+ I = CI;
+ return *this;
+ }
+
+ llvm::Instruction *get() const {
+ assert(I && "Unexpected nullptr!");
+ return I;
+ }
+ operator llvm::Instruction *() const { return asInstruction(); }
+ llvm::Instruction *operator->() const { return get(); }
+
+ explicit operator bool() const { return isInstruction(); }
+ bool operator!() const { return isNull(); }
+
+ llvm::Value *getValueOperand() const {
+ if (isLoad())
+ return asLoad();
+ if (isStore())
+ return asStore()->getValueOperand();
+ if (isMemIntrinsic())
+ return nullptr;
+ if (isCallInst())
+ return nullptr;
+ llvm_unreachable("Operation not supported on nullptr");
+ }
+ llvm::Value *getPointerOperand() const {
+ if (isLoad())
+ return asLoad()->getPointerOperand();
+ if (isStore())
+ return asStore()->getPointerOperand();
+ if (isMemIntrinsic())
+ return asMemIntrinsic()->getRawDest();
+ if (isCallInst())
+ return nullptr;
+ llvm_unreachable("Operation not supported on nullptr");
+ }
+
+ unsigned getAlignment() const {
+ if (isLoad())
+ return asLoad()->getAlignment();
+ if (isStore())
+ return asStore()->getAlignment();
+ if (isMemTransferInst())
+ return std::min(asMemTransferInst()->getDestAlignment(),
+ asMemTransferInst()->getSourceAlignment());
+ if (isMemIntrinsic())
+ return asMemIntrinsic()->getDestAlignment();
+ if (isCallInst())
+ return 0;
+ llvm_unreachable("Operation not supported on nullptr");
+ }
+ bool isVolatile() const {
+ if (isLoad())
+ return asLoad()->isVolatile();
+ if (isStore())
+ return asStore()->isVolatile();
+ if (isMemIntrinsic())
+ return asMemIntrinsic()->isVolatile();
+ if (isCallInst())
+ return false;
+ llvm_unreachable("Operation not supported on nullptr");
+ }
+ bool isSimple() const {
+ if (isLoad())
+ return asLoad()->isSimple();
+ if (isStore())
+ return asStore()->isSimple();
+ if (isMemIntrinsic())
+ return !asMemIntrinsic()->isVolatile();
+ if (isCallInst())
+ return true;
+ llvm_unreachable("Operation not supported on nullptr");
+ }
+ llvm::AtomicOrdering getOrdering() const {
+ if (isLoad())
+ return asLoad()->getOrdering();
+ if (isStore())
+ return asStore()->getOrdering();
+ if (isMemIntrinsic())
+ return llvm::AtomicOrdering::NotAtomic;
+ if (isCallInst())
+ return llvm::AtomicOrdering::NotAtomic;
+ llvm_unreachable("Operation not supported on nullptr");
+ }
+ bool isUnordered() const {
+ if (isLoad())
+ return asLoad()->isUnordered();
+ if (isStore())
+ return asStore()->isUnordered();
+ // Copied from the Load/Store implementation of isUnordered:
+ if (isMemIntrinsic())
+ return !asMemIntrinsic()->isVolatile();
+ if (isCallInst())
+ return true;
+ llvm_unreachable("Operation not supported on nullptr");
+ }
+
+ bool isNull() const { return !I; }
+ bool isInstruction() const { return I; }
+
+ llvm::Instruction *asInstruction() const { return I; }
+
+private:
+ bool isLoad() const { return I && llvm::isa<llvm::LoadInst>(I); }
+ bool isStore() const { return I && llvm::isa<llvm::StoreInst>(I); }
+ bool isCallInst() const { return I && llvm::isa<llvm::CallInst>(I); }
+ bool isMemIntrinsic() const { return I && llvm::isa<llvm::MemIntrinsic>(I); }
+ bool isMemSetInst() const { return I && llvm::isa<llvm::MemSetInst>(I); }
+ bool isMemTransferInst() const {
+ return I && llvm::isa<llvm::MemTransferInst>(I);
+ }
+
+ llvm::LoadInst *asLoad() const { return llvm::cast<llvm::LoadInst>(I); }
+ llvm::StoreInst *asStore() const { return llvm::cast<llvm::StoreInst>(I); }
+ llvm::CallInst *asCallInst() const { return llvm::cast<llvm::CallInst>(I); }
+ llvm::MemIntrinsic *asMemIntrinsic() const {
+ return llvm::cast<llvm::MemIntrinsic>(I);
+ }
+ llvm::MemSetInst *asMemSetInst() const {
+ return llvm::cast<llvm::MemSetInst>(I);
+ }
+ llvm::MemTransferInst *asMemTransferInst() const {
+ return llvm::cast<llvm::MemTransferInst>(I);
+ }
+};
+} // namespace polly
+
+namespace llvm {
+/// Specialize simplify_type for MemAccInst to enable dyn_cast and cast
+/// from a MemAccInst object.
+template <> struct simplify_type<polly::MemAccInst> {
+ typedef Instruction *SimpleType;
+ static SimpleType getSimplifiedValue(polly::MemAccInst &I) {
+ return I.asInstruction();
+ }
+};
+} // namespace llvm
+
+namespace polly {
+
+/// Simplify the region to have a single unconditional entry edge and a
+/// single exit edge.
+///
+/// Although this function allows DT and RI to be null, regions only work
+/// properly if the DominatorTree (for Region::contains) and RegionInfo are kept
+/// up-to-date.
+///
+/// @param R The region to be simplified
+/// @param DT DominatorTree to be updated.
+/// @param LI LoopInfo to be updated.
+/// @param RI RegionInfo to be updated.
+void simplifyRegion(llvm::Region *R, llvm::DominatorTree *DT,
+ llvm::LoopInfo *LI, llvm::RegionInfo *RI);
+
+/// Split the entry block of a function to store the newly inserted
+/// allocations outside of all Scops.
+///
+/// @param EntryBlock The entry block of the current function.
+/// @param P The pass that currently running.
+///
+void splitEntryBlockForAlloca(llvm::BasicBlock *EntryBlock, llvm::Pass *P);
+
+/// Split the entry block of a function to store the newly inserted
+/// allocations outside of all Scops.
+///
+/// @param DT DominatorTree to be updated.
+/// @param LI LoopInfo to be updated.
+/// @param RI RegionInfo to be updated.
+void splitEntryBlockForAlloca(llvm::BasicBlock *EntryBlock,
+ llvm::DominatorTree *DT, llvm::LoopInfo *LI,
+ llvm::RegionInfo *RI);
+
+/// Wrapper for SCEVExpander extended to all Polly features.
+///
+/// This wrapper will internally call the SCEVExpander but also makes sure that
+/// all additional features not represented in SCEV (e.g., SDiv/SRem are not
+/// black boxes but can be part of the function) will be expanded correctly.
+///
+/// The parameters are the same as for the creation of a SCEVExpander as well
+/// as the call to SCEVExpander::expandCodeFor:
+///
+/// @param S The current Scop.
+/// @param SE The Scalar Evolution pass.
+/// @param DL The module data layout.
+/// @param Name The suffix added to the new instruction names.
+/// @param E The expression for which code is actually generated.
+/// @param Ty The type of the resulting code.
+/// @param IP The insertion point for the new code.
+/// @param VMap A remapping of values used in @p E.
+/// @param RTCBB The last block of the RTC. Used to insert loop-invariant
+/// instructions in rare cases.
+llvm::Value *expandCodeFor(Scop &S, llvm::ScalarEvolution &SE,
+ const llvm::DataLayout &DL, const char *Name,
+ const llvm::SCEV *E, llvm::Type *Ty,
+ llvm::Instruction *IP, ValueMapT *VMap,
+ llvm::BasicBlock *RTCBB);
+
+/// Check if the block is a error block.
+///
+/// A error block is currently any block that fulfills at least one of
+/// the following conditions:
+///
+/// - It is terminated by an unreachable instruction
+/// - It contains a call to a non-pure function that is not immediately
+/// dominated by a loop header and that does not dominate the region exit.
+/// This is a heuristic to pick only error blocks that are conditionally
+/// executed and can be assumed to be not executed at all without the domains
+/// being available.
+///
+/// @param BB The block to check.
+/// @param R The analyzed region.
+/// @param LI The loop info analysis.
+/// @param DT The dominator tree of the function.
+///
+/// @return True if the block is a error block, false otherwise.
+bool isErrorBlock(llvm::BasicBlock &BB, const llvm::Region &R,
+ llvm::LoopInfo &LI, const llvm::DominatorTree &DT);
+
+/// Return the condition for the terminator @p TI.
+///
+/// For unconditional branches the "i1 true" condition will be returned.
+///
+/// @param TI The terminator to get the condition from.
+///
+/// @return The condition of @p TI and nullptr if none could be extracted.
+llvm::Value *getConditionFromTerminator(llvm::Instruction *TI);
+
+/// Get the smallest loop that contains @p S but is not in @p S.
+llvm::Loop *getLoopSurroundingScop(Scop &S, llvm::LoopInfo &LI);
+
+/// Get the number of blocks in @p L.
+///
+/// The number of blocks in a loop are the number of basic blocks actually
+/// belonging to the loop, as well as all single basic blocks that the loop
+/// exits to and which terminate in an unreachable instruction. We do not
+/// allow such basic blocks in the exit of a scop, hence they belong to the
+/// scop and represent run-time conditions which we want to model and
+/// subsequently speculate away.
+///
+/// @see getRegionNodeLoop for additional details.
+unsigned getNumBlocksInLoop(llvm::Loop *L);
+
+/// Get the number of blocks in @p RN.
+unsigned getNumBlocksInRegionNode(llvm::RegionNode *RN);
+
+/// Return the smallest loop surrounding @p RN.
+llvm::Loop *getRegionNodeLoop(llvm::RegionNode *RN, llvm::LoopInfo &LI);
+
+/// Check if @p LInst can be hoisted in @p R.
+///
+/// @param LInst The load to check.
+/// @param R The analyzed region.
+/// @param LI The loop info.
+/// @param SE The scalar evolution analysis.
+/// @param DT The dominator tree of the function.
+/// @param KnownInvariantLoads The invariant load set.
+///
+/// @return True if @p LInst can be hoisted in @p R.
+bool isHoistableLoad(llvm::LoadInst *LInst, llvm::Region &R, llvm::LoopInfo &LI,
+ llvm::ScalarEvolution &SE, const llvm::DominatorTree &DT,
+ const InvariantLoadsSetTy &KnownInvariantLoads);
+
+/// Return true iff @p V is an intrinsic that we ignore during code
+/// generation.
+bool isIgnoredIntrinsic(const llvm::Value *V);
+
+/// Check whether a value an be synthesized by the code generator.
+///
+/// Some value will be recalculated only from information that is code generated
+/// from the polyhedral representation. For such instructions we do not need to
+/// ensure that their operands are available during code generation.
+///
+/// @param V The value to check.
+/// @param S The current SCoP.
+/// @param SE The scalar evolution database.
+/// @param Scope Location where the value would by synthesized.
+/// @return If the instruction I can be regenerated from its
+/// scalar evolution representation, return true,
+/// otherwise return false.
+bool canSynthesize(const llvm::Value *V, const Scop &S,
+ llvm::ScalarEvolution *SE, llvm::Loop *Scope);
+
+/// Return the block in which a value is used.
+///
+/// For normal instructions, this is the instruction's parent block. For PHI
+/// nodes, this is the incoming block of that use, because this is where the
+/// operand must be defined (i.e. its definition dominates this block).
+/// Non-instructions do not use operands at a specific point such that in this
+/// case this function returns nullptr.
+llvm::BasicBlock *getUseBlock(const llvm::Use &U);
+
+// If the loop is nonaffine/boxed, return the first non-boxed surrounding loop
+// for Polly. If the loop is affine, return the loop itself.
+//
+// @param L Pointer to the Loop object to analyze.
+// @param LI Reference to the LoopInfo.
+// @param BoxedLoops Set of Boxed Loops we get from the SCoP.
+llvm::Loop *getFirstNonBoxedLoopFor(llvm::Loop *L, llvm::LoopInfo &LI,
+ const BoxedLoopsSetTy &BoxedLoops);
+
+// If the Basic Block belongs to a loop that is nonaffine/boxed, return the
+// first non-boxed surrounding loop for Polly. If the loop is affine, return
+// the loop itself.
+//
+// @param BB Pointer to the Basic Block to analyze.
+// @param LI Reference to the LoopInfo.
+// @param BoxedLoops Set of Boxed Loops we get from the SCoP.
+llvm::Loop *getFirstNonBoxedLoopFor(llvm::BasicBlock *BB, llvm::LoopInfo &LI,
+ const BoxedLoopsSetTy &BoxedLoops);
+
+/// Is the given instruction a call to a debug function?
+///
+/// A debug function can be used to insert output in Polly-optimized code which
+/// normally does not allow function calls with side-effects. For instance, a
+/// printf can be inserted to check whether a value still has the expected value
+/// after Polly generated code:
+///
+/// int sum = 0;
+/// for (int i = 0; i < 16; i+=1) {
+/// sum += i;
+/// printf("The value of sum at i=%d is %d\n", sum, i);
+/// }
+bool isDebugCall(llvm::Instruction *Inst);
+
+/// Does the statement contain a call to a debug function?
+///
+/// Such a statement must not be removed, even if has no side-effects.
+bool hasDebugCall(ScopStmt *Stmt);
+} // namespace polly
+#endif
diff --git a/linux-x64/clang/include/polly/Support/ScopLocation.h b/linux-x64/clang/include/polly/Support/ScopLocation.h
new file mode 100644
index 0000000..a6d5779
--- /dev/null
+++ b/linux-x64/clang/include/polly/Support/ScopLocation.h
@@ -0,0 +1,34 @@
+//=== ScopLocation.h -- Debug location helper for ScopDetection -*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// Helper function for extracting region debug information.
+//
+//===----------------------------------------------------------------------===//
+//
+#ifndef POLLY_SCOP_LOCATION_H
+#define POLLY_SCOP_LOCATION_H
+
+#include <string>
+
+namespace llvm {
+class Region;
+} // namespace llvm
+
+namespace polly {
+
+/// Get the location of a region from the debug info.
+///
+/// @param R The region to get debug info for.
+/// @param LineBegin The first line in the region.
+/// @param LineEnd The last line in the region.
+/// @param FileName The filename where the region was defined.
+void getDebugLocation(const llvm::Region *R, unsigned &LineBegin,
+ unsigned &LineEnd, std::string &FileName);
+} // namespace polly
+
+#endif // POLLY_SCOP_LOCATION_H
diff --git a/linux-x64/clang/include/polly/Support/VirtualInstruction.h b/linux-x64/clang/include/polly/Support/VirtualInstruction.h
new file mode 100644
index 0000000..90bf04f
--- /dev/null
+++ b/linux-x64/clang/include/polly/Support/VirtualInstruction.h
@@ -0,0 +1,344 @@
+//===------ VirtualInstruction.cpp ------------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// Tools for determining which instructions are within a statement and the
+// nature of their operands.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef POLLY_SUPPORT_VIRTUALINSTRUCTION_H
+#define POLLY_SUPPORT_VIRTUALINSTRUCTION_H
+
+#include "polly/ScopInfo.h"
+
+namespace polly {
+
+/// Determine the nature of a value's use within a statement.
+///
+/// These are not always representable by llvm::Use. For instance, scalar write
+/// MemoryAccesses do use a value, but are not associated with an instruction's
+/// argument.
+///
+/// Despite its name it is not tied to virtual instructions (although it works
+/// fine with them), but to promote consistent handling of values used in
+/// statements.
+class VirtualUse {
+public:
+ /// The different types of uses. Handling usually differentiates a lot between
+ /// these; one can use a switch to handle each case (and get warned by the
+ /// compiler if one is not handled).
+ enum UseKind {
+ // An llvm::Constant.
+ Constant,
+
+ // An llvm::BasicBlock.
+ Block,
+
+ // A value that can be generated using ScopExpander.
+ Synthesizable,
+
+ // A load that always reads the same value throughout the SCoP (address and
+ // the value located there a SCoP-invariant) and has been hoisted in front
+ // of the SCoP.
+ Hoisted,
+
+ // Definition before the SCoP and not synthesizable. Can be an instruction
+ // outside the SCoP, a function argument or a global value. Whether there is
+ // a scalar MemoryAccess in this statement for reading it depends on the
+ // -polly-analyze-read-only-scalars switch.
+ ReadOnly,
+
+ // A definition within the same statement. No MemoryAccess between
+ // definition and use are necessary.
+ Intra,
+
+ // Definition in another statement. There is a scalar MemoryAccess that
+ // makes it available in this statement.
+ Inter
+ };
+
+private:
+ /// The statement where a value is used.
+ ScopStmt *User;
+
+ /// The value that is used.
+ Value *Val;
+
+ /// The type of value use.
+ UseKind Kind;
+
+ /// The value represented as llvm::SCEV expression.
+ const SCEV *ScevExpr;
+
+ /// If this is an inter-statement (or read-only) use, contains the
+ /// MemoryAccess that makes the value available in this statement. In case of
+ /// intra-statement uses, can contain a MemoryKind::Array access. In all other
+ /// cases, it is a nullptr.
+ MemoryAccess *InputMA;
+
+ VirtualUse(ScopStmt *User, Value *Val, UseKind Kind, const SCEV *ScevExpr,
+ MemoryAccess *InputMA)
+ : User(User), Val(Val), Kind(Kind), ScevExpr(ScevExpr), InputMA(InputMA) {
+ }
+
+public:
+ /// Get a VirtualUse for an llvm::Use.
+ ///
+ /// @param S The Scop object.
+ /// @param U The llvm::Use the get information for.
+ /// @param LI The LoopInfo analysis. Needed to determine whether the
+ /// value is synthesizable.
+ /// @param Virtual Whether to ignore existing MemoryAcccess.
+ ///
+ /// @return The VirtualUse representing the same use as @p U.
+ static VirtualUse create(Scop *S, const Use &U, LoopInfo *LI, bool Virtual);
+
+ /// Get a VirtualUse for uses within statements.
+ ///
+ /// It is assumed that the user is not a PHINode. Such uses are always
+ /// VirtualUse::Inter unless in a regions statement.
+ ///
+ /// @param S The Scop object.
+ /// @param UserStmt The statement in which @p Val is used. Can be nullptr, in
+ /// which case it assumed that the statement has been
+ /// removed, which is only possible if no instruction in it
+ /// had side-effects or computes a value used by another
+ /// statement.
+ /// @param UserScope Loop scope in which the value is used. Needed to
+ /// determine whether the value is synthesizable.
+ /// @param Val The value being used.
+ /// @param Virtual Whether to use (and prioritize over instruction location)
+ /// information about MemoryAccesses.
+ ///
+ /// @return A VirtualUse object that gives information about @p Val's use in
+ /// @p UserStmt.
+ static VirtualUse create(Scop *S, ScopStmt *UserStmt, Loop *UserScope,
+ Value *Val, bool Virtual);
+
+ static VirtualUse create(ScopStmt *UserStmt, Loop *UserScope, Value *Val,
+ bool Virtual) {
+ return create(UserStmt->getParent(), UserStmt, UserScope, Val, Virtual);
+ }
+
+ bool isConstant() const { return Kind == Constant; }
+ bool isBlock() const { return Kind == Block; }
+ bool isSynthesizable() const { return Kind == Synthesizable; }
+ bool isHoisted() const { return Kind == Hoisted; }
+ bool isReadOnly() const { return Kind == ReadOnly; }
+ bool isIntra() const { return Kind == Intra; }
+ bool isInter() const { return Kind == Inter; }
+
+ /// Return user statement.
+ ScopStmt *getUser() const { return User; }
+
+ /// Return the used value.
+ llvm::Value *getValue() const { return Val; }
+
+ /// Return the type of use.
+ UseKind getKind() const { return Kind; }
+
+ /// Return the ScalarEvolution representation of @p Val.
+ const SCEV *getScevExpr() const { return ScevExpr; }
+
+ /// Return the MemoryAccess that makes the value available in this statement,
+ /// if any.
+ MemoryAccess *getMemoryAccess() const { return InputMA; }
+
+ /// Print a description of this object.
+ ///
+ /// @param OS Stream to print to.
+ /// @param Reproducible If true, ensures that the output is stable between
+ /// runs and is suitable to check in regression tests.
+ /// This excludes printing e.g. pointer values. If false,
+ /// the output should not be used for regression tests,
+ /// but may contain more information useful in debugger
+ /// sessions.
+ void print(raw_ostream &OS, bool Reproducible = true) const;
+
+#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
+ void dump() const;
+#endif
+};
+
+/// An iterator for virtual operands.
+class VirtualOperandIterator
+ : public std::iterator<std::forward_iterator_tag, VirtualUse> {
+ friend class VirtualInstruction;
+ friend class VirtualUse;
+
+ using super = std::iterator<std::forward_iterator_tag, VirtualUse>;
+ using Self = VirtualOperandIterator;
+
+ ScopStmt *User;
+ User::op_iterator U;
+
+ VirtualOperandIterator(ScopStmt *User, User::op_iterator U)
+ : User(User), U(U) {}
+
+public:
+ using pointer = typename super::pointer;
+ using reference = typename super::reference;
+
+ inline bool operator==(const Self &that) const {
+ assert(this->User == that.User);
+ return this->U == that.U;
+ }
+
+ inline bool operator!=(const Self &that) const {
+ assert(this->User == that.User);
+ return this->U != that.U;
+ }
+
+ VirtualUse operator*() const {
+ return VirtualUse::create(User, User->getSurroundingLoop(), U->get(), true);
+ }
+
+ Use *operator->() const { return U; }
+
+ Self &operator++() {
+ U++;
+ return *this;
+ }
+
+ Self operator++(int) {
+ Self tmp = *this;
+ ++*this;
+ return tmp;
+ }
+};
+
+/// This class represents a "virtual instruction", an instruction in a ScopStmt,
+/// effectively a ScopStmt/Instruction-pair.
+///
+/// An instructions can be moved between statements (e.g. to avoid a scalar
+/// dependency) and even can be contained in multiple statements (for instance,
+/// to recompute a value instead of transferring it), hence 'virtual'. This
+/// class is required to represent such instructions that are not in their
+/// 'physical' location anymore.
+///
+/// A statement can currently not contain the same instructions multiple times
+/// (that is, from different loop iterations). Therefore, a
+/// ScopStmt/Instruction-pair uniquely identifies a virtual instructions.
+/// ScopStmt::getInstruction() can contain the same instruction multiple times,
+/// but they necessarily compute the same value.
+class VirtualInstruction {
+ friend class VirtualOperandIterator;
+ friend struct llvm::DenseMapInfo<VirtualInstruction>;
+
+private:
+ /// The statement this virtual instruction is in.
+ ScopStmt *Stmt = nullptr;
+
+ /// The instruction of a statement.
+ Instruction *Inst = nullptr;
+
+public:
+ VirtualInstruction() {}
+
+ /// Create a new virtual instruction of an instruction @p Inst in @p Stmt.
+ VirtualInstruction(ScopStmt *Stmt, Instruction *Inst)
+ : Stmt(Stmt), Inst(Inst) {
+ assert(Stmt && Inst);
+ }
+
+ VirtualOperandIterator operand_begin() const {
+ return VirtualOperandIterator(Stmt, Inst->op_begin());
+ }
+
+ VirtualOperandIterator operand_end() const {
+ return VirtualOperandIterator(Stmt, Inst->op_end());
+ }
+
+ /// Returns a list of virtual operands.
+ ///
+ /// Virtual operands, like virtual instructions, need to encode the ScopStmt
+ /// they are in.
+ llvm::iterator_range<VirtualOperandIterator> operands() const {
+ return {operand_begin(), operand_end()};
+ }
+
+ /// Return the SCoP everything is contained in.
+ Scop *getScop() const { return Stmt->getParent(); }
+
+ /// Return the ScopStmt this virtual instruction is in.
+ ScopStmt *getStmt() const { return Stmt; }
+
+ /// Return the instruction in the statement.
+ Instruction *getInstruction() const { return Inst; }
+
+ /// Print a description of this object.
+ ///
+ /// @param OS Stream to print to.
+ /// @param Reproducible If true, ensures that the output is stable between
+ /// runs and is suitable for checks in regression tests.
+ /// This excludes printing e.g., pointer values. If false,
+ /// the output should not be used for regression tests,
+ /// but may contain more information useful in debugger
+ /// sessions.
+ void print(raw_ostream &OS, bool Reproducible = true) const;
+
+#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
+ void dump() const;
+#endif
+};
+
+static inline bool operator==(VirtualInstruction LHS, VirtualInstruction RHS) {
+ return LHS.getStmt() == RHS.getStmt() &&
+ LHS.getInstruction() == RHS.getInstruction();
+}
+
+/// Find all reachable instructions and accesses.
+///
+/// @param S The SCoP to find everything reachable in.
+/// @param LI LoopInfo required for analysis.
+/// @param UsedInsts[out] Receives all reachable instructions.
+/// @param UsedAccs[out] Receives all reachable accesses.
+/// @param OnlyLocal If non-nullptr, activates local mode: The SCoP is
+/// assumed to consist only of this statement and is
+/// conservatively correct. Does not require walking the
+/// whole SCoP.
+void markReachable(Scop *S, LoopInfo *LI,
+ DenseSet<VirtualInstruction> &UsedInsts,
+ DenseSet<MemoryAccess *> &UsedAccs,
+ ScopStmt *OnlyLocal = nullptr);
+} // namespace polly
+
+namespace llvm {
+/// Support VirtualInstructions in llvm::DenseMaps.
+template <> struct DenseMapInfo<polly::VirtualInstruction> {
+public:
+ static bool isEqual(polly::VirtualInstruction LHS,
+ polly::VirtualInstruction RHS) {
+ return DenseMapInfo<polly::ScopStmt *>::isEqual(LHS.getStmt(),
+ RHS.getStmt()) &&
+ DenseMapInfo<Instruction *>::isEqual(LHS.getInstruction(),
+ RHS.getInstruction());
+ }
+
+ static polly::VirtualInstruction getTombstoneKey() {
+ polly::VirtualInstruction TombstoneKey;
+ TombstoneKey.Stmt = DenseMapInfo<polly::ScopStmt *>::getTombstoneKey();
+ TombstoneKey.Inst = DenseMapInfo<Instruction *>::getTombstoneKey();
+ return TombstoneKey;
+ }
+
+ static polly::VirtualInstruction getEmptyKey() {
+ polly::VirtualInstruction EmptyKey;
+ EmptyKey.Stmt = DenseMapInfo<polly::ScopStmt *>::getEmptyKey();
+ EmptyKey.Inst = DenseMapInfo<Instruction *>::getEmptyKey();
+ return EmptyKey;
+ }
+
+ static unsigned getHashValue(polly::VirtualInstruction Val) {
+ return DenseMapInfo<std::pair<polly::ScopStmt *, Instruction *>>::
+ getHashValue(std::make_pair(Val.getStmt(), Val.getInstruction()));
+ }
+};
+} // namespace llvm
+
+#endif /* POLLY_SUPPORT_VIRTUALINSTRUCTION_H */