24408765437

Committed 14 Apr 2026 03:47PM UTC coverage: 64.417% (-0.05%) from 64.469%

Build # 24408765437

Build Type

push

github

Committed by

web-flow

Commit Message

Add support for DDE to remove mallocs and frees as dead-code when DataOffloadingNodes operate on them (#678)

 + generic modeling for libNodes to declare that an input pointer does not actually escape through them
 + draft of generic modeling of input-pointer access ranges and access types (read-only, full overwrite etc.)
 + DDE: Offload-Transfer-specific handling to reinterpret their fake output edges instead as only indirect writes vie the target pointer
 + DDE: option to disable all the legacy code that requires full UserAnalysis and DataDependencyAnalysis.
 * the new malloc/heap removal in DDE can now remove containers by itself, not relying on DataDependencyAnalysis for that
 * improved builder.clear_node, node can report how to deal with a dead edge, including calling an update method on the node to make it validate again after edge removal.
 + Used for OffloadTransfer nodes to support removing the output edge via dead-code and drop the transfer and maybe the entire node if it does nothing anymore.
 * Offloading: option to quickly disable omitting d2h for read-only data

Coverage Stats

92 of 162 new or added lines in 11 files covered. (56.79%)

4 existing lines in 3 files now uncovered.

30598 of 47500 relevant lines covered (64.42%)

582.72 hits per line

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

0.0

/sdfg/include/sdfg/data_flow/data_flow_node.h

/**
 * @file data_flow_node.h
 * @brief Base class for all nodes in the dataflow graph
 *
 * DataFlowNode is the abstract base class for all nodes that can appear in a dataflow
 * graph. It provides the fundamental interface for nodes including vertex management,
 * parent graph access, validation, and cloning.
 *
 * ## Key Concepts
 *
 * ### Node Hierarchy
 * The node hierarchy is:
 * - DataFlowNode (abstract base)
 *   - AccessNode: Data access points (variables, arrays)
 *     - ConstantNode: Constant literal values
 *   - CodeNode: Computational operations (abstract)
 *     - Tasklet: Simple operations (add, mul, etc.)
 *     - LibraryNode: Complex operations (BLAS, etc.)
 *
 * ### Graph Vertex
 * Each node is associated with a Boost graph vertex that represents its position
 * in the dataflow graph. The vertex is used for graph traversal and edge management.
 *
 * ### Parent Graph
 * Each node maintains a reference to its parent DataFlowGraph, which owns the node
 * and manages its lifetime and connections.
 *
 * ## Example Usage
 *
 * Working with nodes through the base interface:
 * @code
 * // Get the node's vertex for graph operations
 * graph::Vertex v = node.vertex();
 *
 * // Get the parent dataflow graph
 * DataFlowGraph& graph = node.get_parent();
 *
 * // Check incoming/outgoing edges
 * size_t in_degree = graph.in_degree(node);
 * size_t out_degree = graph.out_degree(node);
 *
 * // Validate the node
 * node.validate(function);
 * @endcode
 *
 * @see AccessNode for data access nodes
 * @see CodeNode for computational nodes
 * @see DataFlowGraph for the container graph
 * @see Element for the base element class
 */

#pragma once

#include <boost/lexical_cast.hpp>
#include <nlohmann/json.hpp>

#include "sdfg/element.h"
#include "sdfg/graph/graph.h"

using json = nlohmann::json;

namespace sdfg {

namespace builder {
class SDFGBuilder;
class StructuredSDFGBuilder;
} // namespace builder

namespace data_flow {

enum class EdgeRemoveOption {
    /** You must not remove this edge unless you can guarantee the entire node will be removed **/
    NotRemovable,
    /**
     * You may remove the edge without further action
     **/
    Trivially,
    /**
     * It can be removed, but the node requires a call to update itself to match the removed edge
     **/
    RequiresUpdate,
    /**
     * This is the only relevant edge of this node. If it will be removed, the entire node must be removed as well,
     * ignoring any potential side-effect flags of the node
     **/
    RemoveNodeAfter
};

class DataFlowGraph;
class Memlet;

/**
 * @class DataFlowNode
 * @brief Abstract base class for all dataflow graph nodes
 *
 * DataFlowNode provides the core interface for all nodes in the dataflow graph.
 * Key responsibilities:
 * - Vertex management: Each node has a unique graph vertex
 * - Parent graph access: Nodes know their containing graph
 * - Validation: Abstract interface for semantic validation
 * - Cloning: Abstract interface for creating node copies
 *
 * This is an abstract class and cannot be instantiated directly.
 * Use derived classes like AccessNode, Tasklet, or LibraryNode.
 */
class DataFlowNode : public Element {
    friend class sdfg::builder::SDFGBuilder;
    friend class sdfg::builder::StructuredSDFGBuilder;

private:
    // Remark: Exclusive resource
    graph::Vertex vertex_; ///< Graph vertex representing this node's position

    DataFlowGraph* parent_; ///< Parent dataflow graph that owns this node

protected:
    /**
     * @brief Protected constructor for dataflow nodes
     * @param element_id Unique element identifier
     * @param debug_info Debug information for this node
     * @param vertex Graph vertex for this node
     * @param parent Parent dataflow graph
     */
    DataFlowNode(size_t element_id, const DebugInfo& debug_info, const graph::Vertex vertex, DataFlowGraph& parent);

public:
    // Remark: Exclusive resource
    DataFlowNode(const DataFlowNode& data_node) = delete;
    DataFlowNode& operator=(const DataFlowNode&) = delete;

    /**
     * @brief Check if this node has side effects
     * Side effect on dflow nodes is broad. It just means it cannot be removed just because there are no more direct
     * consumers in the dataflow But underneath, a accessNode-write is considered as having a side effect for this
     * purpose. Closer inspection of access nodes could show those side effects as being irrelevant if never read and
     * fully owned
     */
    [[nodiscard]] virtual bool side_effect() const = 0;

    /**
     * @brief Get the graph vertex for this node
     * @return The Boost graph vertex representing this node
     */
    graph::Vertex vertex() const;

    /**
     * @brief Get the parent dataflow graph (const)
     * @return Const reference to the parent DataFlowGraph
     */
    const DataFlowGraph& get_parent() const;

    /**
     * @brief Get the parent dataflow graph (mutable)
     * @return Mutable reference to the parent DataFlowGraph
     */
    DataFlowGraph& get_parent();

    /**
     * @brief Clone this node for graph transformations
     * @param element_id New element identifier for the clone
     * @param vertex New graph vertex for the clone
     * @param parent Parent graph for the clone
     * @return Unique pointer to the cloned node
     *
     * Pure virtual function that must be implemented by derived classes
     * to support graph transformations and optimizations.
     */
    virtual std::unique_ptr<DataFlowNode> clone(size_t element_id, const graph::Vertex vertex, DataFlowGraph& parent)
        const = 0;

    /**
     * Is the edge in question removable, or will this make the node its an output on invalid?
     * Currently, some nodes may require every out connector to have at least 1 connection attached
     * @return NotRemovable, NoDependencies, CustomRemove
     *
     * [NotRemovable] means only if the entire node can be removed, can the edge be removed
     * [NoDependencies] means, the edge can be removed trivially, the node will work without for the remaining functions
     * [CustomRemove] means, a call to [remove_out_edge] can have the node remove the edge itself and make necessary
     */
    virtual EdgeRemoveOption can_remove_out_edge(const data_flow::DataFlowGraph& graph, const Memlet* memlet) const = 0;

    /**
     *
     * @param out_conn a output connector, whose edge was just removed after approval via [can_remove_out_edge] ==
     * EdgeRemoveOption::RequiresUpdate
     * @return edge removal is completed, node is valid without edge
     */
    virtual bool update_edge_removed(const std::string& out_conn) { return false; }
};
} // namespace data_flow
} // namespace sdfg

1	/**
2	* @file data_flow_node.h
3	* @brief Base class for all nodes in the dataflow graph
4	*
5	* DataFlowNode is the abstract base class for all nodes that can appear in a dataflow
6	* graph. It provides the fundamental interface for nodes including vertex management,
7	* parent graph access, validation, and cloning.
8	*
9	* ## Key Concepts
10	*
11	* ### Node Hierarchy
12	* The node hierarchy is:
13	* - DataFlowNode (abstract base)
14	* - AccessNode: Data access points (variables, arrays)
15	* - ConstantNode: Constant literal values
16	* - CodeNode: Computational operations (abstract)
17	* - Tasklet: Simple operations (add, mul, etc.)
18	* - LibraryNode: Complex operations (BLAS, etc.)
19	*
20	* ### Graph Vertex
21	* Each node is associated with a Boost graph vertex that represents its position
22	* in the dataflow graph. The vertex is used for graph traversal and edge management.
23	*
24	* ### Parent Graph
25	* Each node maintains a reference to its parent DataFlowGraph, which owns the node
26	* and manages its lifetime and connections.
27	*
28	* ## Example Usage
29	*
30	* Working with nodes through the base interface:
31	* @code
32	* // Get the node's vertex for graph operations
33	* graph::Vertex v = node.vertex();
34	*
35	* // Get the parent dataflow graph
36	* DataFlowGraph& graph = node.get_parent();
37	*
38	* // Check incoming/outgoing edges
39	* size_t in_degree = graph.in_degree(node);
40	* size_t out_degree = graph.out_degree(node);
41	*
42	* // Validate the node
43	* node.validate(function);
44	* @endcode
45	*
46	* @see AccessNode for data access nodes
47	* @see CodeNode for computational nodes
48	* @see DataFlowGraph for the container graph
49	* @see Element for the base element class
50	*/
51
52	#pragma once
53
54	#include <boost/lexical_cast.hpp>
55	#include <nlohmann/json.hpp>
56
57	#include "sdfg/element.h"
58	#include "sdfg/graph/graph.h"
59
60	using json = nlohmann::json;
61
62	namespace sdfg {
63
64	namespace builder {
65	class SDFGBuilder;
66	class StructuredSDFGBuilder;
67	} // namespace builder
68
69	namespace data_flow {
70
71	enum class EdgeRemoveOption {
72	/ You must not remove this edge unless you can guarantee the entire node will be removed /
73	NotRemovable,
74	/**
75	* You may remove the edge without further action
76	**/
77	Trivially,
78	/**
79	* It can be removed, but the node requires a call to update itself to match the removed edge
80	**/
81	RequiresUpdate,
82	/**
83	* This is the only relevant edge of this node. If it will be removed, the entire node must be removed as well,
84	* ignoring any potential side-effect flags of the node
85	**/
86	RemoveNodeAfter
87	};
88
89	class DataFlowGraph;
90	class Memlet;
91
92	/**
93	* @class DataFlowNode
94	* @brief Abstract base class for all dataflow graph nodes
95	*
96	* DataFlowNode provides the core interface for all nodes in the dataflow graph.
97	* Key responsibilities:
98	* - Vertex management: Each node has a unique graph vertex
99	* - Parent graph access: Nodes know their containing graph
100	* - Validation: Abstract interface for semantic validation
101	* - Cloning: Abstract interface for creating node copies
102	*
103	* This is an abstract class and cannot be instantiated directly.
104	* Use derived classes like AccessNode, Tasklet, or LibraryNode.
105	*/
106	class DataFlowNode : public Element {
107	friend class sdfg::builder::SDFGBuilder;
108	friend class sdfg::builder::StructuredSDFGBuilder;
109
110	private:
111	// Remark: Exclusive resource
112	graph::Vertex vertex_; ///< Graph vertex representing this node's position
113
114	DataFlowGraph* parent_; ///< Parent dataflow graph that owns this node
115
116	protected:
117	/**
118	* @brief Protected constructor for dataflow nodes
119	* @param element_id Unique element identifier
120	* @param debug_info Debug information for this node
121	* @param vertex Graph vertex for this node
122	* @param parent Parent dataflow graph
123	*/
124	DataFlowNode(size_t element_id, const DebugInfo& debug_info, const graph::Vertex vertex, DataFlowGraph& parent);
125
126	public:
127	// Remark: Exclusive resource
128	DataFlowNode(const DataFlowNode& data_node) = delete;
129	DataFlowNode& operator=(const DataFlowNode&) = delete;
130
131	/**
132	* @brief Check if this node has side effects
133	* Side effect on dflow nodes is broad. It just means it cannot be removed just because there are no more direct
134	* consumers in the dataflow But underneath, a accessNode-write is considered as having a side effect for this
135	* purpose. Closer inspection of access nodes could show those side effects as being irrelevant if never read and
136	* fully owned
137	*/
138	[[nodiscard]] virtual bool side_effect() const = 0;
139
140	/**
141	* @brief Get the graph vertex for this node
142	* @return The Boost graph vertex representing this node
143	*/
144	graph::Vertex vertex() const;
145
146	/**
147	* @brief Get the parent dataflow graph (const)
148	* @return Const reference to the parent DataFlowGraph
149	*/
150	const DataFlowGraph& get_parent() const;
151
152	/**
153	* @brief Get the parent dataflow graph (mutable)
154	* @return Mutable reference to the parent DataFlowGraph
155	*/
156	DataFlowGraph& get_parent();
157
158	/**
159	* @brief Clone this node for graph transformations
160	* @param element_id New element identifier for the clone
161	* @param vertex New graph vertex for the clone
162	* @param parent Parent graph for the clone
163	* @return Unique pointer to the cloned node
164	*
165	* Pure virtual function that must be implemented by derived classes
166	* to support graph transformations and optimizations.
167	*/
168	virtual std::unique_ptr<DataFlowNode> clone(size_t element_id, const graph::Vertex vertex, DataFlowGraph& parent)
169	const = 0;
170
171	/**
172	* Is the edge in question removable, or will this make the node its an output on invalid?
173	* Currently, some nodes may require every out connector to have at least 1 connection attached
174	* @return NotRemovable, NoDependencies, CustomRemove
175	*
176	* [NotRemovable] means only if the entire node can be removed, can the edge be removed
177	* [NoDependencies] means, the edge can be removed trivially, the node will work without for the remaining functions
178	* [CustomRemove] means, a call to [remove_out_edge] can have the node remove the edge itself and make necessary
179	*/
180	virtual EdgeRemoveOption can_remove_out_edge(const data_flow::DataFlowGraph& graph, const Memlet* memlet) const = 0;
181
182	/**
183	*
184	* @param out_conn a output connector, whose edge was just removed after approval via [can_remove_out_edge] ==
185	* EdgeRemoveOption::RequiresUpdate
186	* @return edge removal is completed, node is valid without edge
187	*/
NEW 188	virtual bool update_edge_removed(const std::string& out_conn) { return false; }	×
189	};
190	} // namespace data_flow
191	} // namespace sdfg

daisytuner / docc / 24408765437

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