159 lines
4.8 KiB
C++
159 lines
4.8 KiB
C++
#ifndef PFOR_PFOR_PARALLELIZABLE_H
|
|
#define PFOR_PFOR_PARALLELIZABLE_H
|
|
|
|
#include "expression/access.h"
|
|
#include "expression/algorithm.h"
|
|
#include "expression/info.h"
|
|
#include "expression/operandtag.h"
|
|
#include "expression/tagger.h"
|
|
#include "index/properties.h"
|
|
#include "index/traits.h"
|
|
#include "lineardiophantineequation.h"
|
|
#include "mp/pack.h"
|
|
|
|
namespace pfor {
|
|
|
|
namespace impl {
|
|
|
|
template<typename Index>
|
|
struct IsLinearOrInjective: std::integral_constant<bool,
|
|
index::isLinear<std::decay_t<Index>> or index::isInjective<std::decay_t<Index>>
|
|
> {};
|
|
|
|
/**
|
|
* @brief true if all indices are linear or injective
|
|
*/
|
|
template<typename... Indices>
|
|
constexpr bool allLinearOrInjective = packAll<Pack<Indices...>, IsLinearOrInjective>;
|
|
|
|
}
|
|
|
|
/**
|
|
*/
|
|
template<typename, typename, typename, typename=void> struct TestVariable;
|
|
|
|
/*
|
|
* if all indices are not either linear or at least injective, default to sequential
|
|
*/
|
|
template<typename Id, expr::Access access, typename Index, typename IncludeList, typename... Ts>
|
|
struct TestVariable<expr::OperandTag<Id, access, Index>, IncludeList, Pack<Ts...>,
|
|
std::enable_if_t<
|
|
not index::allLinear<Index, typename Ts::Index...> and
|
|
not impl::allLinearOrInjective<Index, typename Ts::Index...>
|
|
>
|
|
>
|
|
{
|
|
static constexpr bool value = false;
|
|
};
|
|
|
|
/*
|
|
* if not only linear expressions for indices, defaults to Fw = emptyset or |F| = 1
|
|
* when non linear still are injective
|
|
*/
|
|
template<typename Id, expr::Access access, typename Index, typename IncludeList, typename... Ts>
|
|
struct TestVariable<expr::OperandTag<Id, access, Index>, IncludeList, Pack<Ts...>,
|
|
std::enable_if_t<
|
|
not index::allLinear<Index, typename Ts::Index...> and
|
|
impl::allLinearOrInjective<Index, typename Ts::Index...>
|
|
>
|
|
>
|
|
{
|
|
using First = expr::OperandTag<Id, access, Index>;
|
|
using Indices = PackUniq<typename expr::IncludeTagsImpl<Id, Pack<First, Ts...>>::indices>;
|
|
|
|
static constexpr std::size_t cwrite = expr::countWrite<IncludeList>;
|
|
static constexpr std::size_t cindices = PackSize<Indices>::value;
|
|
|
|
static constexpr bool value = (cwrite == 0 || (cwrite == 1 && cindices == 1));
|
|
};
|
|
|
|
/*
|
|
* if only linear expressions for indices, use linear diophantine equations
|
|
*/
|
|
template<typename First, typename IncludeList, typename... Ts>
|
|
struct TestVariable<First, IncludeList, Pack<Ts...>,
|
|
std::enable_if_t<index::allLinear<typename First::Index, typename Ts::Index...>>
|
|
>
|
|
{
|
|
using wtags = expr::FilterOperandTags<Pack<First, Ts...>, expr::Access::write>;
|
|
using wit = expr::IndicesFromOperandTags<wtags>;
|
|
using allit = expr::IndicesFromOperandTags<IncludeList>;
|
|
static constexpr bool value = noLinearDiophantineSolutionForGrid<wit, allit>;
|
|
};
|
|
|
|
template<typename First, typename IncludeList, typename... Ts>
|
|
constexpr bool testVariable = TestVariable<First, IncludeList, Ts...>::value;
|
|
|
|
/**
|
|
* ConstantWriteAccess
|
|
*/
|
|
template<typename> struct HasConstantWriteAccess;
|
|
|
|
template<typename Id, typename Index, typename... Ts>
|
|
struct HasConstantWriteAccess<Pack<expr::OperandTag<Id, expr::Access::write, Index>, Ts...>> {
|
|
static constexpr bool value = index::isConstant<Index> || HasConstantWriteAccess<Pack<Ts...>>::value;
|
|
};
|
|
|
|
template<typename Id, typename Index, typename... Ts>
|
|
struct HasConstantWriteAccess<Pack<expr::OperandTag<Id, expr::Access::read, Index>, Ts...>> {
|
|
static constexpr bool value = HasConstantWriteAccess<Pack<Ts...>>::value;
|
|
};
|
|
|
|
template<>
|
|
struct HasConstantWriteAccess<Pack<>> {
|
|
static constexpr bool value = false;
|
|
};
|
|
|
|
template<typename P>
|
|
constexpr bool hasConstantWriteAccess = HasConstantWriteAccess<P>::value;
|
|
|
|
/**
|
|
* RWControl
|
|
*/
|
|
template<typename> struct RWControl;
|
|
|
|
template<typename Id, expr::Access access, typename Index, typename... Ts>
|
|
struct RWControl<Pack<expr::OperandTag<Id, access, Index>, Ts...>> {
|
|
using First = expr::OperandTag<Id, access, Index>;
|
|
using IncludeList = expr::IncludeTags<Id, Pack<First, Ts...>>;
|
|
using ExcludeList = expr::ExcludeTags<Id, Pack<First, Ts...>>;
|
|
|
|
static constexpr bool noConstantWrite = !hasConstantWriteAccess<IncludeList>;
|
|
static constexpr bool noIndexConflict = testVariable<First, IncludeList, Pack<Ts...>>;
|
|
|
|
static constexpr bool value = noConstantWrite && noIndexConflict && RWControl<ExcludeList>::value;
|
|
};
|
|
|
|
template<>
|
|
struct RWControl<Pack<>> {
|
|
static constexpr bool value = true;
|
|
};
|
|
|
|
template<typename Tags>
|
|
constexpr bool rwControl = RWControl<Tags>::value;
|
|
|
|
/**
|
|
* Parallelizable
|
|
*/
|
|
template<typename> struct Parallelizable;
|
|
|
|
template<typename Op, typename... Ts>
|
|
struct Parallelizable<expr::Expression<Op, Ts...>> {
|
|
using tags = expr::ExpressionTagger<expr::Expression<Op, Ts...>>;
|
|
using filtered_tags = expr::ExcludeTags<expr::IgnoredId, tags>;
|
|
|
|
static constexpr bool value = rwControl<filtered_tags>;
|
|
};
|
|
|
|
/**
|
|
* @param[in] E an expression
|
|
*
|
|
* @return true if the expression can be run in parallel
|
|
*/
|
|
template<typename E>
|
|
constexpr bool parallelizable = Parallelizable<E>::value;
|
|
|
|
}
|
|
|
|
#endif
|