21098544716

Committed 17 Jan 2026 05:57PM UTC coverage: 64.664% (-0.06%) from 64.728%

Build # 21098544716

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #459 from daisytuner/isl-tiling

Adds OMPScheduler and PollyScheduler

Run Details

220 of 375 new or added lines in 13 files covered. (58.67%)

44 existing lines in 2 files now uncovered.

19129 of 29582 relevant lines covered (64.66%)

788.2 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

50.0

/opt/src/transformations/polly_transform.cpp

//===- ScheduleOptimizer.cpp - Calculate an optimized schedule ------------===//
//
// 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 pass generates an entirely new schedule tree from the data dependences
// and iteration domains. The new schedule tree is computed in two steps:
//
// 1) The isl scheduling optimizer is run
//
// The isl scheduling optimizer creates a new schedule tree that maximizes
// parallelism and tileability and minimizes data-dependence distances. The
// algorithm used is a modified version of the ``Pluto'' algorithm:
//
//   U. Bondhugula, A. Hartono, J. Ramanujam, and P. Sadayappan.
//   A Practical Automatic Polyhedral Parallelizer and Locality Optimizer.
//   In Proceedings of the 2008 ACM SIGPLAN Conference On Programming Language
//   Design and Implementation, PLDI ’08, pages 101–113. ACM, 2008.
//
// 2) A set of post-scheduling transformations is applied on the schedule tree.
//
// These optimizations include:
//
//  - Tiling of the innermost tilable bands
//  - Prevectorization - The choice of a possible outer loop that is strip-mined
//                       to the innermost level to enable inner-loop
//                       vectorization.
//  - Some optimizations for spatial locality are also planned.
//
// For a detailed description of the schedule tree itself please see section 6
// of:
//
// Polyhedral AST generation is more than scanning polyhedra
// Tobias Grosser, Sven Verdoolaege, Albert Cohen
// ACM Transactions on Programming Languages and Systems (TOPLAS),
// 37(4), July 2015
// http://www.grosser.es/#pub-polyhedral-AST-generation
//
// This publication also contains a detailed discussion of the different options
// for polyhedral loop unrolling, full/partial tile separation and other uses
// of the schedule tree.
//
//===----------------------------------------------------------------------===//
//
// This file is based on the original source files which were modified for sdfglib.
//
//===----------------------------------------------------------------------===//
#include "sdfg/transformations/polly_transform.h"

#include <isl/constraint.h>
#include <isl/id.h>
#include <isl/map.h>
#include <isl/schedule_node.h>
#include <isl/space.h>
#include <isl/union_map.h>
#include <isl/union_set.h>
#include <isl/val.h>

namespace sdfg {
namespace transformations {

static bool isSimpleInnermostBand(isl_schedule_node* node) {
    assert(isl_schedule_node_get_type(node) == isl_schedule_node_band);
    assert(isl_schedule_node_n_children(node) == 1);

    isl_schedule_node* child = isl_schedule_node_get_child(node, 0);
    enum isl_schedule_node_type child_type = isl_schedule_node_get_type(child);

    if (child_type == isl_schedule_node_leaf) {
        isl_schedule_node_free(child);
        return true;
    }

    if (child_type != isl_schedule_node_sequence) {
        isl_schedule_node_free(child);
        return false;
    }

    int nc = isl_schedule_node_n_children(child);
    for (int c = 0; c < nc; ++c) {
        isl_schedule_node* seq_child = isl_schedule_node_get_child(child, c);
        if (isl_schedule_node_get_type(seq_child) != isl_schedule_node_filter) {
            isl_schedule_node_free(seq_child);
            isl_schedule_node_free(child);
            return false;
        }

        isl_schedule_node* filter_child = isl_schedule_node_get_child(seq_child, 0);
        bool is_leaf = (isl_schedule_node_get_type(filter_child) == isl_schedule_node_leaf);
        isl_schedule_node_free(filter_child);
        isl_schedule_node_free(seq_child);

        if (!is_leaf) {
            isl_schedule_node_free(child);
            return false;
        }
    }

    isl_schedule_node_free(child);
    return true;
}

static bool isOneTimeParentBandNode(isl_schedule_node* node) {
    if (isl_schedule_node_get_type(node) != isl_schedule_node_band) return false;

    if (isl_schedule_node_n_children(node) != 1) return false;

    return true;
}

static bool isTileableBandNode(isl_schedule_node* node) {
    if (!isOneTimeParentBandNode(node)) return false;

    if (!isl_schedule_node_band_get_permutable(node)) return false;

    isl_space* space = isl_schedule_node_band_get_space(node);
    int dim = isl_space_dim(space, isl_dim_set);
    isl_space_free(space);

    if (dim <= 1) return false;

    return isSimpleInnermostBand(node);
}

static isl_schedule_node* tile_node(isl_ctx* ctx, isl_schedule_node* node, const char* identifier, int default_tile_size) {
    isl_space* space = isl_schedule_node_band_get_space(node);
    int dims = isl_space_dim(space, isl_dim_set);

    isl_multi_val* sizes = isl_multi_val_zero(space);
    std::string identifierString(identifier);
    for (int i = 0; i < dims; ++i) {
        sizes = isl_multi_val_set_val(sizes, i, isl_val_int_from_si(ctx, default_tile_size));
    }

    std::string tileLoopMarkerStr = identifierString + " - Tiles";
    isl_id* tileLoopMarker = isl_id_alloc(ctx, tileLoopMarkerStr.c_str(), nullptr);
    node = isl_schedule_node_insert_mark(node, tileLoopMarker);
    node = isl_schedule_node_child(node, 0);
    node = isl_schedule_node_band_tile(node, sizes);
    node = isl_schedule_node_child(node, 0);

    std::string pointLoopMarkerStr = identifierString + " - Points";
    isl_id* pointLoopMarker = isl_id_alloc(ctx, pointLoopMarkerStr.c_str(), nullptr);

    node = isl_schedule_node_insert_mark(node, pointLoopMarker);
    return isl_schedule_node_child(node, 0);
}

static isl_schedule_node* optimize_band(isl_schedule_node* node, void* User) {
    if (!isTileableBandNode(node)) {
        return node;
    }

    isl_ctx* ctx = isl_schedule_node_get_ctx(node);
    // First level tiling
    node = tile_node(ctx, node, "1st level tiling", 32);

    // Second level tiling
    node = tile_node(ctx, node, "2nd level tiling", 16);

    return node;
}

PollyTransform::PollyTransform(structured_control_flow::StructuredLoop& loop, bool tile)
    : loop_(loop), tile_(tile), scop_(nullptr), dependences_(nullptr) {};

std::string PollyTransform::name() const { return "PollyTransform"; };

bool PollyTransform::can_be_applied(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {
    analysis::ScopBuilder scop_builder(builder.subject(), loop_);
    this->scop_ = scop_builder.build(analysis_manager);
    if (!this->scop_) {
        return false;
    }
    this->dependences_ = std::make_unique<analysis::Dependences>(*this->scop_);
    if (!this->dependences_->has_valid_dependences()) {
        this->dependences_ = nullptr;
        this->scop_ = nullptr;
        return false;
    }

    return true;
};

void PollyTransform::apply(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {
    assert(
        this->scop_ != nullptr && this->dependences_ != nullptr &&
        "PollyTransform::apply called without successful can_be_applied"
    );

    int validity_kinds = analysis::Dependences::TYPE_RAW | analysis::Dependences::TYPE_WAR |
                         analysis::Dependences::TYPE_WAW;
    int proximity_kinds = analysis::Dependences::TYPE_RAW | analysis::Dependences::TYPE_WAR |
                          analysis::Dependences::TYPE_WAW;
    isl_union_map* validity = this->dependences_->dependences(validity_kinds);
    isl_union_map* proximity = this->dependences_->dependences(proximity_kinds);

    isl_union_set* domain = this->scop_->domains();
    validity = isl_union_map_gist_domain(validity, isl_union_set_copy(domain));
    validity = isl_union_map_gist_range(validity, isl_union_set_copy(domain));
    proximity = isl_union_map_gist_domain(proximity, isl_union_set_copy(domain));
    proximity = isl_union_map_gist_range(proximity, isl_union_set_copy(domain));

    // Add spatial proximity
    isl_union_map* spatial_proximity = isl_union_map_empty(isl_union_map_get_space(proximity));

    for (auto* stmt : this->scop_->statements()) {
        for (auto* access : stmt->accesses()) {
            isl_map* rel = access->relation();
            if (isl_map_dim(rel, isl_dim_out) == 0) {
                continue;
            }

            // We create a map that maps each element to the next element in the last dimension
            isl_space* array_space = isl_space_range(isl_map_get_space(rel));
            isl_map* adj = isl_map_universe(isl_space_map_from_set(isl_space_copy(array_space)));

            int n_dim = isl_map_dim(adj, isl_dim_out);
            for (int i = 0; i < n_dim - 1; ++i) {
                adj = isl_map_equate(adj, isl_dim_in, i, isl_dim_out, i);
            }

            isl_local_space* ls = isl_local_space_from_space(isl_map_get_space(adj));
            isl_constraint* c = isl_equality_alloc(ls);
            c = isl_constraint_set_coefficient_si(c, isl_dim_out, n_dim - 1, 1);
            c = isl_constraint_set_coefficient_si(c, isl_dim_in, n_dim - 1, -1);
            c = isl_constraint_set_constant_si(c, -1);
            adj = isl_map_add_constraint(adj, c);

            // S -> Array
            isl_map* rel_map = isl_map_copy(rel);
            // S_next -> Array_next = Array + 1
            // We want S -> S_next such that Acc(S_next) = Acc(S) + 1
            // S -> Acc(S) -> Acc(S)+1 -> S_next
            // Proximity = Rel . Adj . Rel^-1

            isl_map* map = isl_map_apply_range(rel_map, adj);
            map = isl_map_apply_range(map, isl_map_reverse(isl_map_copy(rel)));

            spatial_proximity = isl_union_map_add_map(spatial_proximity, map);

            isl_space_free(array_space);
        }
    }

    proximity = isl_union_map_union(proximity, spatial_proximity);

    int isl_maximize_bands = 1;
    int isl_outer_coincidence = 0;

    isl_options_set_schedule_outer_coincidence(scop_->ctx(), isl_outer_coincidence);
    isl_options_set_schedule_maximize_band_depth(scop_->ctx(), isl_maximize_bands);
    isl_options_set_schedule_max_constant_term(scop_->ctx(), 20);
    isl_options_set_schedule_max_coefficient(scop_->ctx(), 20);
    isl_options_set_tile_scale_tile_loops(scop_->ctx(), 0);

    isl_schedule_constraints* SC = isl_schedule_constraints_on_domain(isl_union_set_copy(domain));
    SC = isl_schedule_constraints_set_proximity(SC, isl_union_map_copy(proximity));
    SC = isl_schedule_constraints_set_validity(SC, isl_union_map_copy(validity));
    SC = isl_schedule_constraints_set_coincidence(SC, isl_union_map_copy(validity));
    isl_schedule* S = isl_schedule_constraints_compute_schedule(SC);

    if (this->tile_) {
        isl_schedule_node* root = isl_schedule_get_root(S);
        root = isl_schedule_node_map_descendant_bottom_up(root, optimize_band, nullptr);
        isl_schedule_free(S);

        S = isl_schedule_node_get_schedule(root);
        isl_schedule_node_free(root);
    }

    scop_->set_schedule_tree(S);

    isl_union_map_free(validity);
    isl_union_map_free(proximity);
    isl_union_set_free(domain);

    DEBUG_PRINTLN("PollyTransform:" << std::endl << scop_->ast());

    auto& sdfg = builder.subject();
    analysis::ScopToSDFG converter(*scop_, *dependences_, builder);
    converter.build(analysis_manager);

    this->applied_ = true;
    this->dependences_ = nullptr;
    this->scop_ = nullptr;
};

void PollyTransform::to_json(nlohmann::json& j) const {
    std::string loop_type;
    if (dynamic_cast<structured_control_flow::For*>(&loop_)) {
        loop_type = "for";
    } else if (dynamic_cast<structured_control_flow::Map*>(&loop_)) {
        loop_type = "map";
    } else {
        throw InvalidSDFGException("Unsupported loop type for serialization of loop: " + loop_.indvar()->get_name());
    }

    j["transformation_type"] = this->name();
    j["subgraph"] = {{"0", {{"element_id", this->loop_.element_id()}, {"type", loop_type}}}};
    j["parameters"] = {{"tile", this->tile_}};
};

PollyTransform PollyTransform::from_json(builder::StructuredSDFGBuilder& builder, const nlohmann::json& desc) {
    auto loop_id = desc["subgraph"]["0"]["element_id"].get<size_t>();
    auto element = builder.find_element_by_id(loop_id);
    if (!element) {
        throw InvalidTransformationDescriptionException("Element with ID " + std::to_string(loop_id) + " not found.");
    }
    auto loop = dynamic_cast<structured_control_flow::StructuredLoop*>(element);
    bool tile = desc["parameters"]["tile"].get<bool>();

    return PollyTransform(*loop, tile);
};

} // namespace transformations
} // namespace sdfg

1	//===- ScheduleOptimizer.cpp - Calculate an optimized schedule ------------===//
2	//
3	// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4	// See https://llvm.org/LICENSE.txt for license information.
5	// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6	//
7	//===----------------------------------------------------------------------===//
8	//
9	// This pass generates an entirely new schedule tree from the data dependences
10	// and iteration domains. The new schedule tree is computed in two steps:
11	//
12	// 1) The isl scheduling optimizer is run
13	//
14	// The isl scheduling optimizer creates a new schedule tree that maximizes
15	// parallelism and tileability and minimizes data-dependence distances. The
16	// algorithm used is a modified version of the ``Pluto'' algorithm:
17	//
18	// U. Bondhugula, A. Hartono, J. Ramanujam, and P. Sadayappan.
19	// A Practical Automatic Polyhedral Parallelizer and Locality Optimizer.
20	// In Proceedings of the 2008 ACM SIGPLAN Conference On Programming Language
21	// Design and Implementation, PLDI ’08, pages 101–113. ACM, 2008.
22	//
23	// 2) A set of post-scheduling transformations is applied on the schedule tree.
24	//
25	// These optimizations include:
26	//
27	// - Tiling of the innermost tilable bands
28	// - Prevectorization - The choice of a possible outer loop that is strip-mined
29	// to the innermost level to enable inner-loop
30	// vectorization.
31	// - Some optimizations for spatial locality are also planned.
32	//
33	// For a detailed description of the schedule tree itself please see section 6
34	// of:
35	//
36	// Polyhedral AST generation is more than scanning polyhedra
37	// Tobias Grosser, Sven Verdoolaege, Albert Cohen
38	// ACM Transactions on Programming Languages and Systems (TOPLAS),
39	// 37(4), July 2015
40	// http://www.grosser.es/#pub-polyhedral-AST-generation
41	//
42	// This publication also contains a detailed discussion of the different options
43	// for polyhedral loop unrolling, full/partial tile separation and other uses
44	// of the schedule tree.
45	//
46	//===----------------------------------------------------------------------===//
47	//
48	// This file is based on the original source files which were modified for sdfglib.
49	//
50	//===----------------------------------------------------------------------===//
51	#include "sdfg/transformations/polly_transform.h"
52
53	#include <isl/constraint.h>
54	#include <isl/id.h>
55	#include <isl/map.h>
56	#include <isl/schedule_node.h>
57	#include <isl/space.h>
58	#include <isl/union_map.h>
59	#include <isl/union_set.h>
60	#include <isl/val.h>
61
62	namespace sdfg {
63	namespace transformations {
64
NEW 65	static bool isSimpleInnermostBand(isl_schedule_node* node) {	×
NEW 66	assert(isl_schedule_node_get_type(node) == isl_schedule_node_band);	×
NEW 67	assert(isl_schedule_node_n_children(node) == 1);	×
68
NEW 69	isl_schedule_node* child = isl_schedule_node_get_child(node, 0);	×
NEW 70	enum isl_schedule_node_type child_type = isl_schedule_node_get_type(child);	×
71
NEW 72	if (child_type == isl_schedule_node_leaf) {	×
NEW 73	isl_schedule_node_free(child);	×
NEW 74	return true;	×
NEW 75	}	×
76
NEW 77	if (child_type != isl_schedule_node_sequence) {	×
NEW 78	isl_schedule_node_free(child);	×
NEW 79	return false;	×
NEW 80	}	×
81
NEW 82	int nc = isl_schedule_node_n_children(child);	×
NEW 83	for (int c = 0; c < nc; ++c) {	×
NEW 84	isl_schedule_node* seq_child = isl_schedule_node_get_child(child, c);	×
NEW 85	if (isl_schedule_node_get_type(seq_child) != isl_schedule_node_filter) {	×
NEW 86	isl_schedule_node_free(seq_child);	×
NEW 87	isl_schedule_node_free(child);	×
NEW 88	return false;	×
NEW 89	}	×
90
NEW 91	isl_schedule_node* filter_child = isl_schedule_node_get_child(seq_child, 0);	×
NEW 92	bool is_leaf = (isl_schedule_node_get_type(filter_child) == isl_schedule_node_leaf);	×
NEW 93	isl_schedule_node_free(filter_child);	×
NEW 94	isl_schedule_node_free(seq_child);	×
95
NEW 96	if (!is_leaf) {	×
NEW 97	isl_schedule_node_free(child);	×
NEW 98	return false;	×
NEW 99	}	×
NEW 100	}	×
101
NEW 102	isl_schedule_node_free(child);	×
NEW 103	return true;	×
NEW 104	}	×
105
NEW 106	static bool isOneTimeParentBandNode(isl_schedule_node* node) {	×
NEW 107	if (isl_schedule_node_get_type(node) != isl_schedule_node_band) return false;	×
108
NEW 109	if (isl_schedule_node_n_children(node) != 1) return false;	×
110
NEW 111	return true;	×
NEW 112	}	×
113
NEW 114	static bool isTileableBandNode(isl_schedule_node* node) {	×
NEW 115	if (!isOneTimeParentBandNode(node)) return false;	×
116
NEW 117	if (!isl_schedule_node_band_get_permutable(node)) return false;	×
118
NEW 119	isl_space* space = isl_schedule_node_band_get_space(node);	×
NEW 120	int dim = isl_space_dim(space, isl_dim_set);	×
NEW 121	isl_space_free(space);	×
122
NEW 123	if (dim <= 1) return false;	×
124
NEW 125	return isSimpleInnermostBand(node);	×
NEW 126	}	×
127
NEW 128	static isl_schedule_node* tile_node(isl_ctx* ctx, isl_schedule_node* node, const char* identifier, int default_tile_size) {	×
NEW 129	isl_space* space = isl_schedule_node_band_get_space(node);	×
NEW 130	int dims = isl_space_dim(space, isl_dim_set);	×
131
NEW 132	isl_multi_val* sizes = isl_multi_val_zero(space);	×
NEW 133	std::string identifierString(identifier);	×
NEW 134	for (int i = 0; i < dims; ++i) {	×
NEW 135	sizes = isl_multi_val_set_val(sizes, i, isl_val_int_from_si(ctx, default_tile_size));	×
NEW 136	}	×
137
NEW 138	std::string tileLoopMarkerStr = identifierString + " - Tiles";	×
NEW 139	isl_id* tileLoopMarker = isl_id_alloc(ctx, tileLoopMarkerStr.c_str(), nullptr);	×
NEW 140	node = isl_schedule_node_insert_mark(node, tileLoopMarker);	×
NEW 141	node = isl_schedule_node_child(node, 0);	×
NEW 142	node = isl_schedule_node_band_tile(node, sizes);	×
NEW 143	node = isl_schedule_node_child(node, 0);	×
144
NEW 145	std::string pointLoopMarkerStr = identifierString + " - Points";	×
NEW 146	isl_id* pointLoopMarker = isl_id_alloc(ctx, pointLoopMarkerStr.c_str(), nullptr);	×
147
NEW 148	node = isl_schedule_node_insert_mark(node, pointLoopMarker);	×
NEW 149	return isl_schedule_node_child(node, 0);	×
NEW 150	}	×
151
NEW 152	static isl_schedule_node* optimize_band(isl_schedule_node* node, void* User) {	×
NEW 153	if (!isTileableBandNode(node)) {	×
NEW 154	return node;	×
NEW 155	}	×
156
NEW 157	isl_ctx* ctx = isl_schedule_node_get_ctx(node);	×
158	// First level tiling
NEW 159	node = tile_node(ctx, node, "1st level tiling", 32);	×
160
161	// Second level tiling
NEW 162	node = tile_node(ctx, node, "2nd level tiling", 16);	×
163
NEW 164	return node;	×
NEW 165	}	×
166
167	PollyTransform::PollyTransform(structured_control_flow::StructuredLoop& loop, bool tile)
168	: loop_(loop), tile_(tile), scop_(nullptr), dependences_(nullptr) {};	14✔
169
170	std::string PollyTransform::name() const { return "PollyTransform"; };	4✔
171
172	bool PollyTransform::can_be_applied(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {	10✔
173	analysis::ScopBuilder scop_builder(builder.subject(), loop_);	10✔
174	this->scop_ = scop_builder.build(analysis_manager);	10✔
175	if (!this->scop_) {	10✔
176	return false;	×
177	}	×
178	this->dependences_ = std::make_unique<analysis::Dependences>(*this->scop_);	10✔
179	if (!this->dependences_->has_valid_dependences()) {	10✔
180	this->dependences_ = nullptr;	×
181	this->scop_ = nullptr;	×
182	return false;	×
183	}	×
184
185	return true;	10✔
186	};	10✔
187
188	void PollyTransform::apply(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {	10✔
189	assert(	10✔
190	this->scop_ != nullptr && this->dependences_ != nullptr &&	10✔
191	"PollyTransform::apply called without successful can_be_applied"	10✔
192	);	10✔
193
194	int validity_kinds = analysis::Dependences::TYPE_RAW \| analysis::Dependences::TYPE_WAR \|	10✔
195	analysis::Dependences::TYPE_WAW;	10✔
196	int proximity_kinds = analysis::Dependences::TYPE_RAW \| analysis::Dependences::TYPE_WAR \|	10✔
197	analysis::Dependences::TYPE_WAW;	10✔
198	isl_union_map* validity = this->dependences_->dependences(validity_kinds);	10✔
199	isl_union_map* proximity = this->dependences_->dependences(proximity_kinds);	10✔
200
201	isl_union_set* domain = this->scop_->domains();	10✔
202	validity = isl_union_map_gist_domain(validity, isl_union_set_copy(domain));	10✔
203	validity = isl_union_map_gist_range(validity, isl_union_set_copy(domain));	10✔
204	proximity = isl_union_map_gist_domain(proximity, isl_union_set_copy(domain));	10✔
205	proximity = isl_union_map_gist_range(proximity, isl_union_set_copy(domain));	10✔
206
207	// Add spatial proximity
208	isl_union_map* spatial_proximity = isl_union_map_empty(isl_union_map_get_space(proximity));	10✔
209
210	for (auto* stmt : this->scop_->statements()) {	10✔
211	for (auto* access : stmt->accesses()) {	20✔
212	isl_map* rel = access->relation();	20✔
213	if (isl_map_dim(rel, isl_dim_out) == 0) {	20✔
214	continue;	×
215	}	×
216
217	// We create a map that maps each element to the next element in the last dimension
218	isl_space* array_space = isl_space_range(isl_map_get_space(rel));	20✔
219	isl_map* adj = isl_map_universe(isl_space_map_from_set(isl_space_copy(array_space)));	20✔
220
221	int n_dim = isl_map_dim(adj, isl_dim_out);	20✔
222	for (int i = 0; i < n_dim - 1; ++i) {	36✔
223	adj = isl_map_equate(adj, isl_dim_in, i, isl_dim_out, i);	16✔
224	}	16✔
225
226	isl_local_space* ls = isl_local_space_from_space(isl_map_get_space(adj));	20✔
227	isl_constraint* c = isl_equality_alloc(ls);	20✔
228	c = isl_constraint_set_coefficient_si(c, isl_dim_out, n_dim - 1, 1);	20✔
229	c = isl_constraint_set_coefficient_si(c, isl_dim_in, n_dim - 1, -1);	20✔
230	c = isl_constraint_set_constant_si(c, -1);	20✔
231	adj = isl_map_add_constraint(adj, c);	20✔
232
233	// S -> Array
234	isl_map* rel_map = isl_map_copy(rel);	20✔
235	// S_next -> Array_next = Array + 1
236	// We want S -> S_next such that Acc(S_next) = Acc(S) + 1
237	// S -> Acc(S) -> Acc(S)+1 -> S_next
238	// Proximity = Rel . Adj . Rel^-1
239
240	isl_map* map = isl_map_apply_range(rel_map, adj);	20✔
241	map = isl_map_apply_range(map, isl_map_reverse(isl_map_copy(rel)));	20✔
242
243	spatial_proximity = isl_union_map_add_map(spatial_proximity, map);	20✔
244
245	isl_space_free(array_space);	20✔
246	}	20✔
247	}	10✔
248
249	proximity = isl_union_map_union(proximity, spatial_proximity);	10✔
250
251	int isl_maximize_bands = 1;	10✔
252	int isl_outer_coincidence = 0;	10✔
253
254	isl_options_set_schedule_outer_coincidence(scop_->ctx(), isl_outer_coincidence);	10✔
255	isl_options_set_schedule_maximize_band_depth(scop_->ctx(), isl_maximize_bands);	10✔
256	isl_options_set_schedule_max_constant_term(scop_->ctx(), 20);	10✔
257	isl_options_set_schedule_max_coefficient(scop_->ctx(), 20);	10✔
258	isl_options_set_tile_scale_tile_loops(scop_->ctx(), 0);	10✔
259
260	isl_schedule_constraints* SC = isl_schedule_constraints_on_domain(isl_union_set_copy(domain));	10✔
261	SC = isl_schedule_constraints_set_proximity(SC, isl_union_map_copy(proximity));	10✔
262	SC = isl_schedule_constraints_set_validity(SC, isl_union_map_copy(validity));	10✔
263	SC = isl_schedule_constraints_set_coincidence(SC, isl_union_map_copy(validity));	10✔
264	isl_schedule* S = isl_schedule_constraints_compute_schedule(SC);	10✔
265
266	if (this->tile_) {	10✔
NEW 267	isl_schedule_node* root = isl_schedule_get_root(S);	×
NEW 268	root = isl_schedule_node_map_descendant_bottom_up(root, optimize_band, nullptr);	×
NEW 269	isl_schedule_free(S);	×
270
NEW 271	S = isl_schedule_node_get_schedule(root);	×
NEW 272	isl_schedule_node_free(root);	×
NEW 273	}	×
274
275	scop_->set_schedule_tree(S);	10✔
276
277	isl_union_map_free(validity);	10✔
278	isl_union_map_free(proximity);	10✔
279	isl_union_set_free(domain);	10✔
280
281	DEBUG_PRINTLN("PollyTransform:" << std::endl << scop_->ast());	10✔
282
283	auto& sdfg = builder.subject();	10✔
284	analysis::ScopToSDFG converter(scop_, dependences_, builder);	10✔
285	converter.build(analysis_manager);	10✔
286
287	this->applied_ = true;	10✔
288	this->dependences_ = nullptr;	10✔
289	this->scop_ = nullptr;	10✔
290	};	10✔
291
292	void PollyTransform::to_json(nlohmann::json& j) const {	2✔
293	std::string loop_type;	2✔
294	if (dynamic_cast<structured_control_flow::For*>(&loop_)) {	2✔
295	loop_type = "for";	×
296	} else if (dynamic_cast<structured_control_flow::Map*>(&loop_)) {	2✔
297	loop_type = "map";	2✔
298	} else {	2✔
299	throw InvalidSDFGException("Unsupported loop type for serialization of loop: " + loop_.indvar()->get_name());	×
300	}	×
301
302	j["transformation_type"] = this->name();	2✔
303	j["subgraph"] = {{"0", {{"element_id", this->loop_.element_id()}, {"type", loop_type}}}};	2✔
304	j["parameters"] = {{"tile", this->tile_}};	2✔
305	};	2✔
306
307	PollyTransform PollyTransform::from_json(builder::StructuredSDFGBuilder& builder, const nlohmann::json& desc) {	2✔
308	auto loop_id = desc["subgraph"]["0"]["element_id"].get<size_t>();	2✔
309	auto element = builder.find_element_by_id(loop_id);	2✔
310	if (!element) {	2✔
311	throw InvalidTransformationDescriptionException("Element with ID " + std::to_string(loop_id) + " not found.");	×
312	}	×
313	auto loop = dynamic_cast<structured_control_flow::StructuredLoop*>(element);	2✔
314	bool tile = desc["parameters"]["tile"].get<bool>();	2✔
315
316	return PollyTransform(*loop, tile);	2✔
317	};	2✔
318
319	} // namespace transformations
320	} // namespace sdfg

daisytuner / sdfglib / 21098544716

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous