26556322966

Committed 27 May 2026 03:45PM UTC coverage: 60.869% (-0.02%) from 60.886%

Build # 26556322966

Build Type

push

github

Committed by

web-flow

Commit Message

Libnode ptr edges (#719)

Migrating SDFGs to treat pointers as inputs to libNodes / Calls as scalars.
A pointer will only appear in an output edge if its actually returned from the function (like malloc).

* Stdlib, Blas and Tensor Matmul nodes were migrated to this new format. Other, currently transitory Tensor Nodes are not yet migrated.
* DOCC version was bumped to incorporate previous docc-llvm versions (up to 0.4.0) that had been counted separately.
! Until all passes consider the use / leak of pointers as uncertainty / hiding potential writes, TensorNodes are declared as general side-effect.
* Lots of utility functions to centralize the creation (and edges) of various libNodes that needed to be changed.
* Fixed & unified docc paths across python and llvm front-ends.
* Skip BlockFusion test that fails to its libNodes currently having side effects
~ Prevent a crash in DotViz when using symbolic offsets into structs
* Removing old ConstProp pass, it is not safe for the new pointer representation and should not be all too critical

Coverage Stats

961 of 1749 new or added lines in 52 files covered. (54.95%)

87 existing lines in 28 files now uncovered.

35225 of 57870 relevant lines covered (60.87%)

11046.32 hits per line

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

29.68

/opt/src/passes/offloading/data_transfer_minimization_pass.cpp

#include "sdfg/passes/offloading/data_transfer_minimization_pass.h"

#include <cstddef>
#include <string>
#include <unordered_set>
#include <utility>

#include "sdfg/analysis/analysis.h"
#include "sdfg/analysis/data_transfer_elimination_analysis.h"
#include "sdfg/analysis/scope_analysis.h"
#include "sdfg/analysis/users.h"
#include "sdfg/data_flow/access_node.h"
#include "sdfg/data_flow/code_node.h"
#include "sdfg/data_flow/data_flow_graph.h"
#include "sdfg/data_flow/library_node.h"
#include "sdfg/data_flow/memlet.h"
#include "sdfg/data_flow/tasklet.h"
#include "sdfg/element.h"
#include "sdfg/exceptions.h"
#include "sdfg/helpers/helpers.h"
#include "sdfg/structured_control_flow/block.h"
#include "sdfg/structured_control_flow/control_flow_node.h"
#include "sdfg/structured_control_flow/sequence.h"
#include "sdfg/symbolic/symbolic.h"
#include "sdfg/targets/cuda/cuda_data_offloading_node.h"
#include "sdfg/targets/offloading/data_offloading_node.h"
#include "sdfg/targets/rocm/rocm_data_offloading_node.h"
#include "sdfg/types/pointer.h"
#include "sdfg/visitor/structured_sdfg_visitor.h"

namespace sdfg {
namespace passes {

DataTransferMinimizationPass::DataTransferMinimizationPass() {}

bool DataTransferMinimizationPass::eliminate_malloc_first_transfer(
    builder::StructuredSDFGBuilder& builder, analysis::OffloadHolder& malloc_holder, analysis::OffloadHolder& copy_in
) {
    // Get all relevant information
    std::string copy_in_device_container = copy_in.dev_data->data();
    DebugInfo copy_in_dst_debinfo = copy_in.dev_data->debug_info();

    // leave the malloc itself, because we have not proven yet that there is no more d2H transfer that needs it
    // DDE needs to be able to find it

    auto* h2d_block = dynamic_cast<structured_control_flow::Block*>(copy_in.offload_node->get_parent().get_parent());
    builder.remove_memlet(*h2d_block, *copy_in.host_access);
    builder.remove_node(*h2d_block, *copy_in.host_data);
    copy_in.remove_h2d_parts();
    copy_in.offload_node->remove_h2d();

    return true;
}

bool DataTransferMinimizationPass::eliminate_redundant_d2h(
    builder::StructuredSDFGBuilder& builder, analysis::OffloadHolder& h2d, analysis::OffloadHolder& d2h
) {
    // Get all relevant information
    std::string copy_out_device_container = d2h.dev_data->data();
    DebugInfo copy_out_dst_debinfo = d2h.dev_data->debug_info();

    // leave the malloc itself, because we have not proven yet that there is no more d2H transfer that needs it
    // DDE needs to be able to find it

    auto* d2h_block = dynamic_cast<structured_control_flow::Block*>(d2h.offload_node->get_parent().get_parent());
    if (d2h.offload_node->is_d2h()) {
        if (d2h.offload_node->is_free()) {
            std::string out_conn = d2h.host_access->src_conn();
            auto access_type = d2h.host_access->base_type().clone();
            builder.remove_memlet(*d2h_block, *d2h.host_access);
            builder.remove_node(*d2h_block, *d2h.host_data);
            d2h.offload_node->remove_d2h();
        } else { // remove it entirely
            builder.clear_code_node_legacy(*d2h_block, *d2h.offload_node);
        }
        d2h.remove_d2h_parts();
        return true;
    } else {
        return false;
    }
}

bool DataTransferMinimizationPass::eliminate_transfer_pair(
    builder::StructuredSDFGBuilder& builder,
    analysis::OffloadHolder& copy_out,
    analysis::OffloadHolder& copy_in,
    bool remove_d2h
) {
    // Get all relevant information
    std::string copy_out_device_container = copy_out.dev_data->data();
    std::string copy_in_device_container = copy_in.dev_data->data();
    DebugInfo copy_out_src_debinfo = copy_out.dev_data->debug_info();
    DebugInfo copy_in_dst_debinfo = copy_in.dev_data->debug_info();

    bool remove_entirely = false;
    // Remove what you can remove
    if (!remove_d2h && copy_out.offload_node->is_free()) {
        if (copy_out.offload_node->is_d2h()) {
            copy_out.offload_node->remove_free();
        } else {
            remove_entirely = true;
        }
    } else if (remove_d2h) {
        remove_entirely = true;
    }
    if (remove_entirely) {
        auto* copy_out_block =
            dynamic_cast<structured_control_flow::Block*>(copy_out.offload_node->get_parent().get_parent());
        builder.clear_code_node_legacy(*copy_out_block, *copy_out.offload_node);
    }

    auto* copy_in_block = dynamic_cast<structured_control_flow::Block*>(copy_in.offload_node->get_parent().get_parent()
    );
    builder.clear_code_node_legacy(*copy_in_block, *copy_in.offload_node);

    // Maps the device pointers if necessary
    if (copy_out_device_container != copy_in_device_container) {
        auto& container_type = builder.subject().type(copy_out_device_container);
        auto ref_type = container_type.clone();
        auto& in_access = builder.add_access(*copy_in_block, copy_out_device_container, copy_out_src_debinfo);
        auto& out_access = builder.add_access(*copy_in_block, copy_in_device_container, copy_in_dst_debinfo);
        builder.add_reference_memlet(
            *copy_in_block,
            in_access,
            out_access,
            {symbolic::zero()},
            *ref_type,
            DebugInfo::merge(copy_out.offload_node->debug_info(), copy_in.offload_node->debug_info())
        );
    }

    return true;
}

bool DataTransferMinimizationPass::
    run_pass(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {
    analysis::DataTransferEliminationAnalysis transfer_analysis(builder.subject(), analysis_manager);
    transfer_analysis.run();

    int removed = 0;

    for (auto& [malloc_cand, first_h2d] : transfer_analysis.empty_malloc_candidates()) {
        auto& malloc_holder = *malloc_cand.offload;

        DEBUG_PRINTLN(
            "  Elim malloc: " << "#" << malloc_holder.malloc_node->element_id() << " -> "
                              << (malloc_holder.host_data ? malloc_holder.host_data->data() : "-") << " / "
                              << "h2d+malloc: #" << first_h2d.offload_node->element_id() << " "
                              << (first_h2d.host_data ? first_h2d.host_data->data() : "-") << " -> "
                              << first_h2d.dev_data->data()
        );

        bool success = eliminate_malloc_first_transfer(builder, malloc_holder, first_h2d);

        if (success) {
            ++removed;
        }
    }

    for (auto& [h2d_cand, redundant_d2h] : transfer_analysis.redundant_d2h_candidates()) {
        auto& h2d_holder = *h2d_cand.offload;

        if (h2d_holder.updates_on_dev) {
            DEBUG_PRINTLN(
                "  Elim h2d: " << "#" << h2d_holder.offload_node->element_id() << " -> " << h2d_holder.host_data->data()
                               << " -> " << h2d_holder.dev_data->data() << " / "
                               << "clean d2h: #" << redundant_d2h.offload_node->element_id() << " "
                               << redundant_d2h.dev_data->data() << " -> " << redundant_d2h.host_data->data()
            );
            bool success = eliminate_redundant_d2h(builder, h2d_holder, redundant_d2h);

            if (success) {
                ++removed;
            }
        }
    }

    for (auto& candidate : transfer_analysis.transfer_reuse_candidates()) {
        auto reads = candidate.first.read_count;
        auto& copy_out = *candidate.first.offload;
        auto& copy_in = candidate.second;
        auto& copy_in_container = copy_in.host_data->data();

        DEBUG_PRINTLN(
            "  Elim hd2: #" << copy_out.offload_node->element_id() << " " << copy_out.dev_data->data() << " -> "
                            << (copy_out.host_data ? copy_out.host_data->data() : "-") << " / "
                            << "d2h: #" << copy_in.offload_node->element_id() << " "
                            << (copy_in.host_data ? copy_in.host_data->data() : "-") << " -> "
                            << copy_in.dev_data->data()
        );

        bool success = eliminate_transfer_pair(builder, copy_out, copy_in, false);

        if (success) {
            ++removed;
        }
    }

    return removed > 0;
}

DataTransferMinimizationLegacy::
    DataTransferMinimizationLegacy(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager)
    : visitor::NonStoppingStructuredSDFGVisitor(builder, analysis_manager) {}

bool DataTransferMinimizationLegacy::visit() {
    DEBUG_PRINTLN("Running DataTransferMinimizationPass on " << this->builder_.subject().name());
    return visitor::NonStoppingStructuredSDFGVisitor::visit();
}

bool DataTransferMinimizationLegacy::accept(structured_control_flow::Sequence& sequence) {
    bool applied = false;
    offloading::DataOffloadingNode* copy_out = nullptr;
    structured_control_flow::Block* copy_out_block = nullptr;
    size_t copy_out_index = 0;

    // While a copy-out can be found:
    while (copy_out_index < sequence.size()) {
        // Find a new copy-out
        for (; copy_out_index < sequence.size(); copy_out_index++) {
            if (auto* block = dynamic_cast<structured_control_flow::Block*>(&sequence.at(copy_out_index).first)) {
                if (block->dataflow().library_nodes().size() == 1 && block->dataflow().tasklets().size() == 0) {
                    auto* libnode = *block->dataflow().library_nodes().begin();
                    if (auto* offloading_node = dynamic_cast<offloading::DataOffloadingNode*>(libnode)) {
                        if (offloading_node->is_d2h()) {
                            copy_out = offloading_node;
                            copy_out_block = block;
                            break;
                        }
                    }
                }
            }
        }

        // Find a matching copy-in
        size_t i;
        for (i = copy_out_index; i < sequence.size(); i++) {
            // Child must be a block
            auto* copy_in_block = dynamic_cast<structured_control_flow::Block*>(&sequence.at(i).first);
            if (!copy_in_block) {
                continue;
            }

            // Block must contain exactly one library node
            if (copy_in_block->dataflow().library_nodes().size() != 1 ||
                copy_in_block->dataflow().tasklets().size() != 0) {
                continue;
            }

            // Library node must be an offloading node
            auto* copy_in =
                dynamic_cast<offloading::DataOffloadingNode*>(*copy_in_block->dataflow().library_nodes().begin());
            if (!copy_in) {
                continue;
            }

            // Offloading node must be a copy-in
            if (!copy_in->is_h2d()) {
                continue;
            }

            // Copy-in and copy-out must be redundant
            if (!copy_out->redundant_with(*copy_in)) {
                continue;
            }

            // Get src and dst access nodes for copy-in & -out
            auto [copy_out_src, copy_out_dst] = this->get_src_and_dst(copy_out_block->dataflow(), copy_out);
            auto [copy_in_src, copy_in_dst] = this->get_src_and_dst(copy_in_block->dataflow(), copy_in);

            // Get the write and read users
            auto& users = this->analysis_manager_.get<analysis::Users>();
            analysis::User* write = users.get_user(copy_out_dst->data(), copy_out_dst, analysis::Use::WRITE);
            if (!write) {
                continue;
            }
            analysis::User* read = users.get_user(copy_in_src->data(), copy_in_src, analysis::Use::READ);
            if (!read) {
                continue;
            }

            if (copy_out_dst->data() == copy_in_src->data()) {
                // Ensure that the container is not written between the data transfer nodes
                bool used_between = false;
                for (auto* user : users.all_uses_between(*write, *read)) {
                    if (user->container() == copy_out_dst->data() && user->use() != analysis::Use::READ) {
                        used_between = true;
                        break;
                    }
                }
                if (used_between) {
                    continue;
                }
            } else {
                if (!this->check_container_dependency(
                        copy_out_block, copy_out_dst->data(), copy_in_block, copy_in_src->data()
                    )) {
                    continue;
                }
            }

            // Check that the container is not written after the data transfer nodes
            bool read_after = false;
            for (auto* user : users.all_uses_after(*write)) {
                if (user->container() == copy_out_dst->data() && user->use() == analysis::Use::READ && user != read) {
                    read_after = true;
                    break;
                }
            }

            // Debug output
            DEBUG_PRINTLN(
                "  Eliminating " << (read_after ? "(" : "") << "copy-out: #" << copy_out->element_id() << " "
                                 << copy_out_src->data() << " -> " << copy_out_dst->data() << (read_after ? ")" : "")
                                 << " / copy-in: #" << copy_in->element_id() << " " << copy_in_src->data() << " -> "
                                 << copy_in_dst->data()
            );

            // Get all relevant information
            std::string copy_out_device_container = copy_out_src->data();
            std::string copy_in_device_container = copy_in_dst->data();
            DebugInfo copy_out_src_debinfo = copy_out_src->debug_info();
            DebugInfo copy_in_dst_debinfo = copy_in_dst->debug_info();

            // Remove the data tranfers
            if (read_after && copy_out->is_free()) {
                copy_out->remove_free();
            } else if (!read_after) {
                this->builder_.clear_code_node_legacy(*copy_out_block, *copy_out);
            }
            this->builder_.clear_code_node_legacy(*copy_in_block, *copy_in);

            // Maps the device pointers if necessary
            if (copy_out_device_container != copy_in_device_container) {
                auto& container_type = this->builder_.subject().type(copy_out_device_container);
                auto ref_type = container_type.clone();
                auto& in_access =
                    this->builder_.add_access(*copy_in_block, copy_out_device_container, copy_out_src_debinfo);
                auto& out_access =
                    this->builder_.add_access(*copy_in_block, copy_in_device_container, copy_in_dst_debinfo);
                this->builder_.add_reference_memlet(
                    *copy_in_block,
                    in_access,
                    out_access,
                    {symbolic::zero()},
                    *ref_type,
                    DebugInfo::merge(copy_out->debug_info(), copy_in->debug_info())
                );
            }

            // Invalidate users analysis
            this->analysis_manager_.invalidate<analysis::Users>();
            applied = true;
            break;
        }

        // Skip if no matching copy-in was found
        if (i >= sequence.size()) {
            copy_out_index++;
        }
    }

    return applied;
}

std::pair<data_flow::AccessNode*, data_flow::AccessNode*> DataTransferMinimizationLegacy::
    get_src_and_dst(data_flow::DataFlowGraph& dfg, offloading::DataOffloadingNode* offloading_node) {
    if (!offloading_node->has_transfer()) {
        throw InvalidSDFGException(
            "DataTransferMinimization: Cannot get copy access nodes for offloading node without data transfers"
        );
    }
    data_flow::AccessNode *src, *dst;
    if (dynamic_cast<cuda::CUDADataOffloadingNode*>(offloading_node)) {
        src = this->get_in_access(offloading_node, "_src");
        dst = this->get_out_access(offloading_node, "_dst");
    } else if (dynamic_cast<rocm::ROCMDataOffloadingNode*>(offloading_node)) {
        src = this->get_in_access(offloading_node, "_src");
        dst = this->get_out_access(offloading_node, "_dst");
    } else {
        throw InvalidSDFGException(
            "DataTransferMinimization: Unknown offloading node encountered: " + offloading_node->code().value()
        );
    }
    return {src, dst};
}

data_flow::AccessNode* DataTransferMinimizationLegacy::
    get_in_access(data_flow::CodeNode* node, const std::string& dst_conn) {
    auto& dfg = node->get_parent();
    for (auto& iedge : dfg.in_edges(*node)) {
        if (iedge.dst_conn() == dst_conn) {
            return dynamic_cast<data_flow::AccessNode*>(&iedge.src());
        }
    }
    return nullptr;
}

data_flow::AccessNode* DataTransferMinimizationLegacy::
    get_out_access(data_flow::CodeNode* node, const std::string& src_conn) {
    auto& dfg = node->get_parent();
    for (auto& oedge : dfg.out_edges(*node)) {
        if (oedge.src_conn() == src_conn) {
            return static_cast<data_flow::AccessNode*>(&oedge.dst());
        }
    }
    return nullptr;
}

bool DataTransferMinimizationLegacy::check_container_dependency(
    structured_control_flow::Block* copy_out_block,
    const std::string& copy_out_container,
    structured_control_flow::Block* copy_in_block,
    const std::string& copy_in_container
) {
    // Simplification: Assume blocks are in the same sequence
    auto& scope_analysis = this->analysis_manager_.get<analysis::ScopeAnalysis>();
    auto* copy_out_block_parent = scope_analysis.parent_scope(copy_out_block);
    auto* copy_in_block_parent = scope_analysis.parent_scope(copy_in_block);
    auto* sequence = dynamic_cast<structured_control_flow::Sequence*>(copy_out_block_parent);
    if (copy_out_block_parent != copy_in_block_parent || !sequence) {
        return false;
    }

    std::unordered_set<std::string> copy_out_container_captures, copy_in_container_parts;
    size_t start = sequence->index(*copy_out_block);
    size_t stop = sequence->index(*copy_in_block);
    for (size_t i = start + 1; i < stop; i++) {
        auto* block = dynamic_cast<structured_control_flow::Block*>(&sequence->at(i).first);
        if (!block) {
            continue;
        }

        auto& dfg = block->dataflow();
        for (auto* access_node : dfg.data_nodes()) {
            if (access_node->data() == copy_in_container) {
                // Only allow constant assignments
                for (auto& iedge : dfg.in_edges(*access_node)) {
                    auto* tasklet = dynamic_cast<data_flow::Tasklet*>(&iedge.src());
                    if (!tasklet || tasklet->code() != data_flow::TaskletCode::assign) {
                        continue;
                    }

                    auto& iedge2 = *dfg.in_edges(*tasklet).begin();
                    if (!dynamic_cast<data_flow::ConstantNode*>(&iedge2.src())) {
                        return false;
                    }
                }

                // Collect H2D container parts
                for (auto& oedge : dfg.out_edges(*access_node)) {
                    if (oedge.type() != data_flow::MemletType::Reference) {
                        continue;
                    }

                    auto* access_node2 = dynamic_cast<data_flow::AccessNode*>(&oedge.dst());
                    if (!access_node2) {
                        continue;
                    }

                    copy_in_container_parts.insert(access_node2->data());
                }
            } else if (access_node->data() == copy_out_container) {
                // Collect D2H container captures
                for (auto& oedge : dfg.out_edges(*access_node)) {
                    if (oedge.type() != data_flow::MemletType::Dereference_Dst) {
                        continue;
                    }

                    auto* access_node2 = dynamic_cast<data_flow::AccessNode*>(&oedge.dst());
                    if (!access_node2) {
                        continue;
                    }

                    copy_out_container_captures.insert(access_node2->data());
                }
            }
        }
    }

    // Find all matches between captures and parts
    size_t matches = 0;
    for (auto& capture : copy_out_container_captures) {
        for (auto& part : copy_in_container_parts) {
            if (capture == part) {
                matches++;
            }
        }
    }

    return (matches == 1);
}

} // namespace passes
} // namespace sdfg

1	#include "sdfg/passes/offloading/data_transfer_minimization_pass.h"
2
3	#include <cstddef>
4	#include <string>
5	#include <unordered_set>
6	#include <utility>
7
8	#include "sdfg/analysis/analysis.h"
9	#include "sdfg/analysis/data_transfer_elimination_analysis.h"
10	#include "sdfg/analysis/scope_analysis.h"
11	#include "sdfg/analysis/users.h"
12	#include "sdfg/data_flow/access_node.h"
13	#include "sdfg/data_flow/code_node.h"
14	#include "sdfg/data_flow/data_flow_graph.h"
15	#include "sdfg/data_flow/library_node.h"
16	#include "sdfg/data_flow/memlet.h"
17	#include "sdfg/data_flow/tasklet.h"
18	#include "sdfg/element.h"
19	#include "sdfg/exceptions.h"
20	#include "sdfg/helpers/helpers.h"
21	#include "sdfg/structured_control_flow/block.h"
22	#include "sdfg/structured_control_flow/control_flow_node.h"
23	#include "sdfg/structured_control_flow/sequence.h"
24	#include "sdfg/symbolic/symbolic.h"
25	#include "sdfg/targets/cuda/cuda_data_offloading_node.h"
26	#include "sdfg/targets/offloading/data_offloading_node.h"
27	#include "sdfg/targets/rocm/rocm_data_offloading_node.h"
28	#include "sdfg/types/pointer.h"
29	#include "sdfg/visitor/structured_sdfg_visitor.h"
30
31	namespace sdfg {
32	namespace passes {
33
34	DataTransferMinimizationPass::DataTransferMinimizationPass() {}	8✔
35
36	bool DataTransferMinimizationPass::eliminate_malloc_first_transfer(
37	builder::StructuredSDFGBuilder& builder, analysis::OffloadHolder& malloc_holder, analysis::OffloadHolder& copy_in
38	) {	3✔
39	// Get all relevant information
40	std::string copy_in_device_container = copy_in.dev_data->data();	3✔
41	DebugInfo copy_in_dst_debinfo = copy_in.dev_data->debug_info();	3✔
42
43	// leave the malloc itself, because we have not proven yet that there is no more d2H transfer that needs it
44	// DDE needs to be able to find it
45
46	auto* h2d_block = dynamic_cast<structured_control_flow::Block*>(copy_in.offload_node->get_parent().get_parent());	3✔
47	builder.remove_memlet(h2d_block, copy_in.host_access);	3✔
48	builder.remove_node(h2d_block, copy_in.host_data);	3✔
49	copy_in.remove_h2d_parts();	3✔
50	copy_in.offload_node->remove_h2d();	3✔
51
52	return true;	3✔
53	}	3✔
54
55	bool DataTransferMinimizationPass::eliminate_redundant_d2h(
56	builder::StructuredSDFGBuilder& builder, analysis::OffloadHolder& h2d, analysis::OffloadHolder& d2h
57	) {	4✔
58	// Get all relevant information
59	std::string copy_out_device_container = d2h.dev_data->data();	4✔
60	DebugInfo copy_out_dst_debinfo = d2h.dev_data->debug_info();	4✔
61
62	// leave the malloc itself, because we have not proven yet that there is no more d2H transfer that needs it
63	// DDE needs to be able to find it
64
65	auto* d2h_block = dynamic_cast<structured_control_flow::Block*>(d2h.offload_node->get_parent().get_parent());	4✔
66	if (d2h.offload_node->is_d2h()) {	4✔
67	if (d2h.offload_node->is_free()) {	4✔
68	std::string out_conn = d2h.host_access->src_conn();	4✔
69	auto access_type = d2h.host_access->base_type().clone();	4✔
70	builder.remove_memlet(d2h_block, d2h.host_access);	4✔
71	builder.remove_node(d2h_block, d2h.host_data);	4✔
72	d2h.offload_node->remove_d2h();	4✔
73	} else { // remove it entirely	4✔
UNCOV 74	builder.clear_code_node_legacy(d2h_block, d2h.offload_node);	×
75	}	×
76	d2h.remove_d2h_parts();	4✔
77	return true;	4✔
78	} else {	4✔
79	return false;	×
80	}	×
81	}	4✔
82
83	bool DataTransferMinimizationPass::eliminate_transfer_pair(
84	builder::StructuredSDFGBuilder& builder,
85	analysis::OffloadHolder& copy_out,
86	analysis::OffloadHolder& copy_in,
87	bool remove_d2h
88	) {	7✔
89	// Get all relevant information
90	std::string copy_out_device_container = copy_out.dev_data->data();	7✔
91	std::string copy_in_device_container = copy_in.dev_data->data();	7✔
92	DebugInfo copy_out_src_debinfo = copy_out.dev_data->debug_info();	7✔
93	DebugInfo copy_in_dst_debinfo = copy_in.dev_data->debug_info();	7✔
94
95	bool remove_entirely = false;	7✔
96	// Remove what you can remove
97	if (!remove_d2h && copy_out.offload_node->is_free()) {	7✔
98	if (copy_out.offload_node->is_d2h()) {	7✔
99	copy_out.offload_node->remove_free();	3✔
100	} else {	4✔
101	remove_entirely = true;	4✔
102	}	4✔
103	} else if (remove_d2h) {	7✔
104	remove_entirely = true;	×
105	}	×
106	if (remove_entirely) {	7✔
107	auto* copy_out_block =	4✔
108	dynamic_cast<structured_control_flow::Block*>(copy_out.offload_node->get_parent().get_parent());	4✔
109	builder.clear_code_node_legacy(copy_out_block, copy_out.offload_node);	4✔
110	}	4✔
111
112	auto* copy_in_block = dynamic_cast<structured_control_flow::Block*>(copy_in.offload_node->get_parent().get_parent()	7✔
113	);	7✔
114	builder.clear_code_node_legacy(copy_in_block, copy_in.offload_node);	7✔
115
116	// Maps the device pointers if necessary
117	if (copy_out_device_container != copy_in_device_container) {	7✔
118	auto& container_type = builder.subject().type(copy_out_device_container);	×
119	auto ref_type = container_type.clone();	×
120	auto& in_access = builder.add_access(*copy_in_block, copy_out_device_container, copy_out_src_debinfo);	×
121	auto& out_access = builder.add_access(*copy_in_block, copy_in_device_container, copy_in_dst_debinfo);	×
122	builder.add_reference_memlet(	×
123	*copy_in_block,	×
124	in_access,	×
125	out_access,	×
126	{symbolic::zero()},	×
127	*ref_type,	×
128	DebugInfo::merge(copy_out.offload_node->debug_info(), copy_in.offload_node->debug_info())	×
129	);	×
130	}	×
131
132	return true;	7✔
133	}	7✔
134
135	bool DataTransferMinimizationPass::
136	run_pass(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {	8✔
137	analysis::DataTransferEliminationAnalysis transfer_analysis(builder.subject(), analysis_manager);	8✔
138	transfer_analysis.run();	8✔
139
140	int removed = 0;	8✔
141
142	for (auto& [malloc_cand, first_h2d] : transfer_analysis.empty_malloc_candidates()) {	8✔
143	auto& malloc_holder = *malloc_cand.offload;	3✔
144
145	DEBUG_PRINTLN(	3✔
146	" Elim malloc: " << "#" << malloc_holder.malloc_node->element_id() << " -> "	3✔
147	<< (malloc_holder.host_data ? malloc_holder.host_data->data() : "-") << " / "	3✔
148	<< "h2d+malloc: #" << first_h2d.offload_node->element_id() << " "	3✔
149	<< (first_h2d.host_data ? first_h2d.host_data->data() : "-") << " -> "	3✔
150	<< first_h2d.dev_data->data()	3✔
151	);	3✔
152
153	bool success = eliminate_malloc_first_transfer(builder, malloc_holder, first_h2d);	3✔
154
155	if (success) {	3✔
156	++removed;	3✔
157	}	3✔
158	}	3✔
159
160	for (auto& [h2d_cand, redundant_d2h] : transfer_analysis.redundant_d2h_candidates()) {	8✔
161	auto& h2d_holder = *h2d_cand.offload;	6✔
162
163	if (h2d_holder.updates_on_dev) {	6✔
164	DEBUG_PRINTLN(	4✔
165	" Elim h2d: " << "#" << h2d_holder.offload_node->element_id() << " -> " << h2d_holder.host_data->data()	4✔
166	<< " -> " << h2d_holder.dev_data->data() << " / "	4✔
167	<< "clean d2h: #" << redundant_d2h.offload_node->element_id() << " "	4✔
168	<< redundant_d2h.dev_data->data() << " -> " << redundant_d2h.host_data->data()	4✔
169	);	4✔
170	bool success = eliminate_redundant_d2h(builder, h2d_holder, redundant_d2h);	4✔
171
172	if (success) {	4✔
173	++removed;	4✔
174	}	4✔
175	}	4✔
176	}	6✔
177
178	for (auto& candidate : transfer_analysis.transfer_reuse_candidates()) {	8✔
179	auto reads = candidate.first.read_count;	7✔
180	auto& copy_out = *candidate.first.offload;	7✔
181	auto& copy_in = candidate.second;	7✔
182	auto& copy_in_container = copy_in.host_data->data();	7✔
183
184	DEBUG_PRINTLN(	7✔
185	" Elim hd2: #" << copy_out.offload_node->element_id() << " " << copy_out.dev_data->data() << " -> "	7✔
186	<< (copy_out.host_data ? copy_out.host_data->data() : "-") << " / "	7✔
187	<< "d2h: #" << copy_in.offload_node->element_id() << " "	7✔
188	<< (copy_in.host_data ? copy_in.host_data->data() : "-") << " -> "	7✔
189	<< copy_in.dev_data->data()	7✔
190	);	7✔
191
192	bool success = eliminate_transfer_pair(builder, copy_out, copy_in, false);	7✔
193
194	if (success) {	7✔
195	++removed;	7✔
196	}	7✔
197	}	7✔
198
199	return removed > 0;	8✔
200	}	8✔
201
202	DataTransferMinimizationLegacy::
203	DataTransferMinimizationLegacy(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager)
204	: visitor::NonStoppingStructuredSDFGVisitor(builder, analysis_manager) {}	×
205
206	bool DataTransferMinimizationLegacy::visit() {	×
207	DEBUG_PRINTLN("Running DataTransferMinimizationPass on " << this->builder_.subject().name());	×
208	return visitor::NonStoppingStructuredSDFGVisitor::visit();	×
209	}	×
210
211	bool DataTransferMinimizationLegacy::accept(structured_control_flow::Sequence& sequence) {	×
212	bool applied = false;	×
213	offloading::DataOffloadingNode* copy_out = nullptr;	×
214	structured_control_flow::Block* copy_out_block = nullptr;	×
215	size_t copy_out_index = 0;	×
216
217	// While a copy-out can be found:
218	while (copy_out_index < sequence.size()) {	×
219	// Find a new copy-out
220	for (; copy_out_index < sequence.size(); copy_out_index++) {	×
221	if (auto* block = dynamic_cast<structured_control_flow::Block*>(&sequence.at(copy_out_index).first)) {	×
222	if (block->dataflow().library_nodes().size() == 1 && block->dataflow().tasklets().size() == 0) {	×
223	auto* libnode = *block->dataflow().library_nodes().begin();	×
224	if (auto* offloading_node = dynamic_cast<offloading::DataOffloadingNode*>(libnode)) {	×
225	if (offloading_node->is_d2h()) {	×
226	copy_out = offloading_node;	×
227	copy_out_block = block;	×
228	break;	×
229	}	×
230	}	×
231	}	×
232	}	×
233	}	×
234
235	// Find a matching copy-in
236	size_t i;	×
237	for (i = copy_out_index; i < sequence.size(); i++) {	×
238	// Child must be a block
239	auto* copy_in_block = dynamic_cast<structured_control_flow::Block*>(&sequence.at(i).first);	×
240	if (!copy_in_block) {	×
241	continue;	×
242	}	×
243
244	// Block must contain exactly one library node
245	if (copy_in_block->dataflow().library_nodes().size() != 1 \|\|	×
246	copy_in_block->dataflow().tasklets().size() != 0) {	×
247	continue;	×
248	}	×
249
250	// Library node must be an offloading node
251	auto* copy_in =	×
252	dynamic_cast<offloading::DataOffloadingNode>(copy_in_block->dataflow().library_nodes().begin());	×
253	if (!copy_in) {	×
254	continue;	×
255	}	×
256
257	// Offloading node must be a copy-in
258	if (!copy_in->is_h2d()) {	×
259	continue;	×
260	}	×
261
262	// Copy-in and copy-out must be redundant
263	if (!copy_out->redundant_with(*copy_in)) {	×
264	continue;	×
265	}	×
266
267	// Get src and dst access nodes for copy-in & -out
268	auto [copy_out_src, copy_out_dst] = this->get_src_and_dst(copy_out_block->dataflow(), copy_out);	×
269	auto [copy_in_src, copy_in_dst] = this->get_src_and_dst(copy_in_block->dataflow(), copy_in);	×
270
271	// Get the write and read users
272	auto& users = this->analysis_manager_.get<analysis::Users>();	×
273	analysis::User* write = users.get_user(copy_out_dst->data(), copy_out_dst, analysis::Use::WRITE);	×
274	if (!write) {	×
275	continue;	×
276	}	×
277	analysis::User* read = users.get_user(copy_in_src->data(), copy_in_src, analysis::Use::READ);	×
278	if (!read) {	×
279	continue;	×
280	}	×
281
282	if (copy_out_dst->data() == copy_in_src->data()) {	×
283	// Ensure that the container is not written between the data transfer nodes
284	bool used_between = false;	×
285	for (auto* user : users.all_uses_between(write, read)) {	×
286	if (user->container() == copy_out_dst->data() && user->use() != analysis::Use::READ) {	×
287	used_between = true;	×
288	break;	×
289	}	×
290	}	×
291	if (used_between) {	×
292	continue;	×
293	}	×
294	} else {	×
295	if (!this->check_container_dependency(	×
296	copy_out_block, copy_out_dst->data(), copy_in_block, copy_in_src->data()	×
297	)) {	×
298	continue;	×
299	}	×
300	}	×
301
302	// Check that the container is not written after the data transfer nodes
303	bool read_after = false;	×
304	for (auto* user : users.all_uses_after(*write)) {	×
305	if (user->container() == copy_out_dst->data() && user->use() == analysis::Use::READ && user != read) {	×
306	read_after = true;	×
307	break;	×
308	}	×
309	}	×
310
311	// Debug output
312	DEBUG_PRINTLN(	×
313	" Eliminating " << (read_after ? "(" : "") << "copy-out: #" << copy_out->element_id() << " "	×
314	<< copy_out_src->data() << " -> " << copy_out_dst->data() << (read_after ? ")" : "")	×
315	<< " / copy-in: #" << copy_in->element_id() << " " << copy_in_src->data() << " -> "	×
316	<< copy_in_dst->data()	×
317	);	×
318
319	// Get all relevant information
320	std::string copy_out_device_container = copy_out_src->data();	×
321	std::string copy_in_device_container = copy_in_dst->data();	×
322	DebugInfo copy_out_src_debinfo = copy_out_src->debug_info();	×
323	DebugInfo copy_in_dst_debinfo = copy_in_dst->debug_info();	×
324
325	// Remove the data tranfers
326	if (read_after && copy_out->is_free()) {	×
327	copy_out->remove_free();	×
328	} else if (!read_after) {	×
329	this->builder_.clear_code_node_legacy(copy_out_block, copy_out);	×
330	}	×
331	this->builder_.clear_code_node_legacy(copy_in_block, copy_in);	×
332
333	// Maps the device pointers if necessary
334	if (copy_out_device_container != copy_in_device_container) {	×
335	auto& container_type = this->builder_.subject().type(copy_out_device_container);	×
336	auto ref_type = container_type.clone();	×
337	auto& in_access =	×
338	this->builder_.add_access(*copy_in_block, copy_out_device_container, copy_out_src_debinfo);	×
339	auto& out_access =	×
340	this->builder_.add_access(*copy_in_block, copy_in_device_container, copy_in_dst_debinfo);	×
341	this->builder_.add_reference_memlet(	×
342	*copy_in_block,	×
343	in_access,	×
344	out_access,	×
345	{symbolic::zero()},	×
346	*ref_type,	×
347	DebugInfo::merge(copy_out->debug_info(), copy_in->debug_info())	×
348	);	×
349	}	×
350
351	// Invalidate users analysis
352	this->analysis_manager_.invalidate<analysis::Users>();	×
353	applied = true;	×
354	break;	×
355	}	×
356
357	// Skip if no matching copy-in was found
358	if (i >= sequence.size()) {	×
359	copy_out_index++;	×
360	}	×
361	}	×
362
363	return applied;	×
364	}	×
365
366	std::pair<data_flow::AccessNode, data_flow::AccessNode> DataTransferMinimizationLegacy::
367	get_src_and_dst(data_flow::DataFlowGraph& dfg, offloading::DataOffloadingNode* offloading_node) {	×
368	if (!offloading_node->has_transfer()) {	×
369	throw InvalidSDFGException(	×
370	"DataTransferMinimization: Cannot get copy access nodes for offloading node without data transfers"	×
371	);	×
372	}	×
373	data_flow::AccessNode src, dst;	×
374	if (dynamic_cast<cuda::CUDADataOffloadingNode*>(offloading_node)) {	×
375	src = this->get_in_access(offloading_node, "_src");	×
376	dst = this->get_out_access(offloading_node, "_dst");	×
377	} else if (dynamic_cast<rocm::ROCMDataOffloadingNode*>(offloading_node)) {	×
378	src = this->get_in_access(offloading_node, "_src");	×
379	dst = this->get_out_access(offloading_node, "_dst");	×
380	} else {	×
381	throw InvalidSDFGException(	×
382	"DataTransferMinimization: Unknown offloading node encountered: " + offloading_node->code().value()	×
383	);	×
384	}	×
385	return {src, dst};	×
386	}	×
387
388	data_flow::AccessNode* DataTransferMinimizationLegacy::
389	get_in_access(data_flow::CodeNode* node, const std::string& dst_conn) {	×
390	auto& dfg = node->get_parent();	×
391	for (auto& iedge : dfg.in_edges(*node)) {	×
392	if (iedge.dst_conn() == dst_conn) {	×
393	return dynamic_cast<data_flow::AccessNode*>(&iedge.src());	×
394	}	×
395	}	×
396	return nullptr;	×
397	}	×
398
399	data_flow::AccessNode* DataTransferMinimizationLegacy::
400	get_out_access(data_flow::CodeNode* node, const std::string& src_conn) {	×
401	auto& dfg = node->get_parent();	×
402	for (auto& oedge : dfg.out_edges(*node)) {	×
403	if (oedge.src_conn() == src_conn) {	×
404	return static_cast<data_flow::AccessNode*>(&oedge.dst());	×
405	}	×
406	}	×
407	return nullptr;	×
408	}	×
409
410	bool DataTransferMinimizationLegacy::check_container_dependency(
411	structured_control_flow::Block* copy_out_block,
412	const std::string& copy_out_container,
413	structured_control_flow::Block* copy_in_block,
414	const std::string& copy_in_container
415	) {	×
416	// Simplification: Assume blocks are in the same sequence
417	auto& scope_analysis = this->analysis_manager_.get<analysis::ScopeAnalysis>();	×
418	auto* copy_out_block_parent = scope_analysis.parent_scope(copy_out_block);	×
419	auto* copy_in_block_parent = scope_analysis.parent_scope(copy_in_block);	×
420	auto* sequence = dynamic_cast<structured_control_flow::Sequence*>(copy_out_block_parent);	×
421	if (copy_out_block_parent != copy_in_block_parent \|\| !sequence) {	×
422	return false;	×
423	}	×
424
425	std::unordered_set<std::string> copy_out_container_captures, copy_in_container_parts;	×
426	size_t start = sequence->index(*copy_out_block);	×
427	size_t stop = sequence->index(*copy_in_block);	×
428	for (size_t i = start + 1; i < stop; i++) {	×
429	auto* block = dynamic_cast<structured_control_flow::Block*>(&sequence->at(i).first);	×
430	if (!block) {	×
431	continue;	×
432	}	×
433
434	auto& dfg = block->dataflow();	×
435	for (auto* access_node : dfg.data_nodes()) {	×
436	if (access_node->data() == copy_in_container) {	×
437	// Only allow constant assignments
438	for (auto& iedge : dfg.in_edges(*access_node)) {	×
439	auto* tasklet = dynamic_cast<data_flow::Tasklet*>(&iedge.src());	×
440	if (!tasklet \|\| tasklet->code() != data_flow::TaskletCode::assign) {	×
441	continue;	×
442	}	×
443
444	auto& iedge2 = dfg.in_edges(tasklet).begin();	×
445	if (!dynamic_cast<data_flow::ConstantNode*>(&iedge2.src())) {	×
446	return false;	×
447	}	×
448	}	×
449
450	// Collect H2D container parts
451	for (auto& oedge : dfg.out_edges(*access_node)) {	×
452	if (oedge.type() != data_flow::MemletType::Reference) {	×
453	continue;	×
454	}	×
455
456	auto* access_node2 = dynamic_cast<data_flow::AccessNode*>(&oedge.dst());	×
457	if (!access_node2) {	×
458	continue;	×
459	}	×
460
461	copy_in_container_parts.insert(access_node2->data());	×
462	}	×
463	} else if (access_node->data() == copy_out_container) {	×
464	// Collect D2H container captures
465	for (auto& oedge : dfg.out_edges(*access_node)) {	×
466	if (oedge.type() != data_flow::MemletType::Dereference_Dst) {	×
467	continue;	×
468	}	×
469
470	auto* access_node2 = dynamic_cast<data_flow::AccessNode*>(&oedge.dst());	×
471	if (!access_node2) {	×
472	continue;	×
473	}	×
474
475	copy_out_container_captures.insert(access_node2->data());	×
476	}	×
477	}	×
478	}	×
479	}	×
480
481	// Find all matches between captures and parts
482	size_t matches = 0;	×
483	for (auto& capture : copy_out_container_captures) {	×
484	for (auto& part : copy_in_container_parts) {	×
485	if (capture == part) {	×
486	matches++;	×
487	}	×
488	}	×
489	}	×
490
491	return (matches == 1);	×
492	}	×
493
494	} // namespace passes
495	} // namespace sdfg

daisytuner / docc / 26556322966

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